Segment Tree 筆記

Segment-Tree 介紹

主要用來找區間最大值或區間總和。由於我是為了這題所以以區間總和做介紹。下面陣列是應對區間總和，每個 node 紀錄的有起始點, 結束點及區間總和，EXAMPLE: [0,4] 代表 index 0 ~ 4 的總和，其總和為 10，[0,0] 代表 index 0~0 也就是 nums[0] 的本身值。至於樹為什麼長這樣跟 Build tree 有關。

    // nums:[-1, 4, 2, 0, 5]
    //
    // Segment Tree for the Above Array:
    //
    //         10                      [0,4]
    //        /  \
    //      5      5           [0,2]          [3,4]
    //     / \    / \
    //    3   2  0   5      [0,1]  [2,2]   [3,3]  [4,4]
    //   / \   
    // -1  4            [0,0]  [1,1]

Segment-Tree 實作

• Build Tree

  這邊我用 c++ 概略作介紹。基本上是 top-down 的 build 法，時間複雜度為 O(n)。

      // Node 資料結構
      class segTreeNode {
      public:
          int begin, end, sum;
          segTreeNode * left = NULL;
          segTreeNode * right = NULL;
          segTreeNode(int s, int e, int m):begin(s), end(e), sum(m) {}
      };
  

      // Build
      segTreeNode* buildSegTree(int begin, int end, vector& nums) {
          // 若 begin = end，代表是 leaf。
          if (begin == end) {
              auto node = new segTreeNode(begin, begin, nums[begin]);
              return node;
          }  
          
          // 分割
          int mid = (begin + end) / 2;
          auto left  = buildSegTree(begin, mid, nums);
          auto right = buildSegTree(mid+1, end, nums);
          auto node = new segTreeNode(begin, end, left->sum + right->sum);
          node->left = left;
          node->right = right;
          return node;
      }
  

• Update tree

  時間複雜度為 O(log n)。

      // Update
      void updateSegTree(segTreeNode* node, int index, int val) {
          
          // 若是該 index 的 leaf。則更新其 sum
          if (node->begin == index && node->end == index) {
              node->sum = val;
              return;
          }
          
          // 若是中間 node 則分割往下繼續找
          int mid = (node->begin + node->end) / 2;
          if (index > mid)
              updateSegTree(node->right, index, val);
          else
              updateSegTree(node->left, index, val);
              
          // 最後更新 node's sum
          node->sum = node->left->sum + node->right->sum;
      }
  

• Sum

  時間複雜度為 O(log n + k)。

      // Sum
      int sumSegTree(segTreeNode* node, int left, int right) {
          // 若完美覆蓋區間，直接回傳。
          if (node->begin == left && node->end == right)
              return node->sum;
          
          int mid = (node->begin + node->end) / 2;
          
          // 要求區間完全在左邊
          if (right <= mid)
              return sumSegTree(node->left, left, right);
          // 要求區間完全在右邊
          else if (left > mid)
              return sumSegTree(node->right, left, right);
          // 兩邊都有
          else
              return sumSegTree(node->left, left, mid) + 
                     sumSegTree(node->right, mid+1, right);
      }
  

參考資料 :

1.leetcode/hg3994 answer

2.youtube 中文講解

Read More

讀書心得 - C++ Primer (5th Edition) - Chapter 5 (3) - 常用詞彙

常用詞彙

• block
  Sequence of zero or more statements enclosed in curly braces. A block is a statement, so it can appear anywhere a statement is expected.
• case label
  Constant expression that follows the keyword case inC++ Primer, Fifth Edition a switch statement. No two case labels in the same switch statement may have the same value.
• catch clause
  The catch keyword, an exception declaration in parentheses, and a block of statements. The code inside a catch clause does whatever is necessary to handle an exception of the type defined in its exception declaration.
• compound statement
  Synonym for block.
• null statement
  An empty statement. Indicated by a single semicolon.
• raise
  Often used as a synonym for throw. C++ programmers speak of “throwing” or “raising” an exception interchangeably.

Read More

讀書心得 - C++ Primer (5th Edition) - Chapter 5 (2) - Exception

Exceptions

Exceptions 是程式在 run-time 遇到的異常，比如與資料庫的連結斷開或遇到其他程式異想不到的 input。Exception handling 基本上就是當程式無法解決問題或者無法繼續執行時發出警告，或者更進一步根據情況處理 exception。

Exception handling 由 detecting, handling parts of a program 所組成

• throw expressions

  當 detecting part 表示遭遇無法處理的情況

• try blocks

  handling part 用來處理 exception。程式碼一開始會有一個 try block 隨後跟著一個或以上的 catch clauses。

• exception classes

  用來傳遞 information about what happened between a throw and an associated catch.

A throw Expression

通常會在 detecting part 發生 exception 時 throw Expression，這麼做原因是有時你不能保證你的程式一定是跟 User 互動的那一個，throw Expression 效果就比你回傳一個錯誤值好用得多。

    // Normal version
    int throwTest(int num1, int num2) {
        if (num1 == num2) {
            cout << "Same." << endl;
            return 0;
        } else {
            cerr << "Not the same." << endl;
            return -1;
        }
    }

    // throw Expression
    void throwTest(int num1, int num2) {
        if (num1 != num2)
            throw runtime_error("Not the same.");
        cout << "Same." << endl;
    }

The try Block

基於 C 風格的錯誤處理，在回傳值代表發生錯誤時予以處理。相比之下 throw 就相對靈活，但也會有終止程式的代價。try catch 的 block 就適合在此情況使用。讓程式有 exception handler。

    try {
        program-statements
    } catch (exception-declaration) {
        handler-statements
    } catch (exception-declaration) {
        handler-statements
    } // . . .

Standard Exceptions

正如上面的 try block 示億程式碼所示，程式必須先宣告 exception 的種類才能近一步去做 handle，這裡紀錄 C++ standard library \ 裡的 exception table。 

    exception         // The most general kind of problem.

    // Runtime errors
    runtime_error     // Problem that can be detected at the run-time.
    range_error       // Result generated outside the range of value that are meaningful.
    overflow_error    // Computation that overflow.
    underflow_error   // Computation that underflow.

    // Logic errors
    logic_error       // Error in the logic of the program.
    domain_error      // Argument for which no result exists.
    invalid_argument  // Inappropriate argument.
    length_error      // Attempt to create an object larger than the maximum size for that type.
    out_of_range      // Use a value outside the valid range.

Read More

讀書心得 - C++ Primer (5th Edition) - Chapter 5 (1) - Statement

Statement

• Simple Statements

  expression 加上 ; 作為結尾視為 statement。

      a + 5  // expression
      a + 5; // statement
      ;      // null statement
  

• Compound Statements (Blocks)

  在 { } 中間一連串的 statements 或 declarations (也允許是空的)，且不用 ; 作為中止符。

      while (val <= 10) {
          sum += val;  // assigns sum + val to sum
          ++val;       // add 1 to val
      }
  

• Statement Scope

  我們可以在 if else for 等等的 statements 裡宣告參數，但該參數也只有在 statements 裡能存取。

      while (int i = get_num()) // i is created and initialized on each iteration
          cout << i << endl;
      i = 0;  // error: i is not accessible outside the loop
  

• Conditional Statements

  有 if statement, if else statement 和 switch statement。以下面的 switch code 為示範，"switch (ch)" 的 ch 為 expression，"case 'a':", "case 'e':" ... 為 case label，當 expression match case label，execution 就會從此開始直到 switch 的中止符或 break，所以是有可能橫跨 case labels。合法 case label 為 integral constant expressions，也就是 integral type 的 constant expression。

      int vowelCnt = 0
      // any occurrence of a, e, i, o, or u increments vowelCnt
      while (cin >> ch) {
          switch (ch) {
              case 'a':
              case 'e':
              case 'i':
              case 'o':
              case 'u':
                  ++vowelCnt;
                  break;
          }
      }
  

• Why can't variables be declared in a switch statement?

  首先這是 stackoverflow 裡的一個問題，問題題目應該改成 Why can't variables be initialized in a switch statement?，因為如果只有 declared 是合法的，頂多有 warning。基本上 case 就是 label 的一種，一種常見於有 goto 的程式碼。若你做 variable definition 在 switch statement，等於在這 switch statement scope 裡會有機會因為做了 goto label 的關係而忽略掉該 definition，進而導致程式碼出錯。若要在 switch statement 做 variable definition，你就必須很明確地告訴 compiler 即使有 goto label 忽略該 variable definition 也沒差，因為我只會在那 case 裡使用，也就是加 {} 更近一步明確地縮小 variable definition 的 scope 而非整個 switch statement scope。(Declaration跟Definition間的差異)

      // Ok, 程式碼寫得漂亮，compiler 發現沒有任何 label 會忽略掉 init 的 definition
      switch (num) {
          case 1:
              int init = 0;
              cout << declare << endl;
      }
  

      // Error, case 2 這個 label 會忽略 init 的 definition
      // main.cpp:17:10: error: jump to case label
      // 17 |     case 2:
      //    |          ^
      switch (num) {
          case 1:
              int init = 0;
              cout << init << endl;
          case 2:
              cout << 9999 << endl;
      }
  

      // 加 {}，縮小該 variable definition 的 scope
      switch (num) {
          case 1:
              {
                  int init = 0;
                  cout << init << endl;
              }
          case 2:
              cout << 9999 << endl;
      }
  

      // 只是 declaration 不會有事
      // 甚至因為是同 scope 所以 case 2 可以呼叫到
      // declare = 5; 若拿掉會出錯
      // 因為 compiler 發現 declare 從沒被賦予值過
      int num = 2;
      switch (num) {
          case 1:
              int declare;
              declare = 5;
          case 2:
              cout << declare << endl;
      }
      // Output: 21911
  

• Iterative Statements

  有 while statement, for statement 跟 do while Statement。C++ 的 for statement 除了傳統的還有 range for statement。其中 expression 必須要是 braced initializer list, array, vector 或 string 其中一種。

      for (declaration : expression)
          statement
  

• Jump Statements

  有 break statement, continue statement 和 goto Statement。

參考資料 :
1.why-cant-variables-be-declared-in-a-switch-statement

Read More