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

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

常用詞彙

• arithmetic conversion
  A conversion from one arithmetic type to another. In the context of the binary arithmetic operators, arithmetic conversions usually attempt to preserve precision by converting a smaller type to a larger type (e.g., integral types are converted to floating point).
• associativity
  Determines how operators with the same precedence are grouped. Operators can be either right associative (operators are grouped from right to left) or left associative (operators are grouped from left to right).
• cast
  An explicit conversion.
• compound expression
  An expression involving more than one operator.
• expression
  The lowest level of computation in a C++ program. Expressions generally apply an operator to one or more operands. Each expression yields a result. Expressions can be used as operands, so we can write compound expressions requiring the evaluation of multiple operators.

Read More

讀書心得 - C++ Primer (5th Edition) - Chapter 4 (2) - Type Conversions

Type Conversions

• Implicit Conversions

  型別轉換，大部分轉換都是看是否能轉換成 int，例如 char, bool, 和 short。

      bool      flag;   char           cval;
      short     sval;   unsigned short usval;
      int       ival;   unsigned int   uival;
      long      lval;   unsigned long  ulval;
      float     fval;   double         dval;
      3.14159L + 'a'; //  'a' promoted to int, then that int converted to long double
      dval + ival;    //  ival converted to double
      dval + fval;    //  fval converted to double
      ival = dval;    //  dval converted (by truncation) to int
      flag = dval;    //  if dval is 0, then flag is false, otherwise true
      cval + fval;    //  cval promoted to int, then that int converted to float
      sval + cval;    //  sval and cval promoted to int
      cval + lval;    //  cval converted to long
      ival + ulval;   //  ival converted to unsigned long
      usval + ival;   //  promotion depends on the size of unsigned short and int
      uival + lval;   //  conversion depends on the size of unsigned int and long
  

• Explicit Conversions

  用於我們想明確地強制將 object 轉換為其他類型。cast-name\(expression)。(const相關文章1, const相關文章2)

      // static_cast 最常用的 cast-name
      // cast used to force floating-point division
      double slope = static_cast<double>(j) / i;
  
      // const_cast 用來改變 low-level const (point to const)
      const char *pc;
      char *p = const_cast<char*>(pc); // ok: but writing through p is undefinedc
  
      // reinterpret_cast 對其 operand 進行 low-level bit 的重新解釋
      // 要很理解其型別的 bit 組成才會使用
      int *ip;
      char *pc = reinterpret_cast<char*>(ip);
  

cast 基本上就是擾亂型別，建議能不使用就不使用。

Read More

讀書心得 - C++ Primer (5th Edition) - Chapter 4 (1) - Expression & Operator

Expression

運算式 (expression) 由運算元 (operand) 與運算子 (operator) 所組成，最終計算產生一個結果 (result)。

• Order of Evaluation

  想要計算 expression 的話，就必須知道運算子運作及其先後順序。這裡的 * 號就不是 pointer 而是相乘，然後再來是基本的先乘除後加減。

      cout << 5 + 10 * 20 / 2 << endl;        // 105
      cout << 6 + 3 * 4 / 2 + 2 << endl;      // 14
      cout << (6 + 3) *  (4 / 2 + 2) << endl; // 36
      cout << ((6 + 3) *  4) / 2 + 2 << endl; // 20
      cout << 6 + 3 * 4  / (2 + 2) << endl;   // 9
  

• Lvalues and Rvalues

  有寫過一篇 Lvalues and Rvalues 也可以參考。這裡紀錄此書寫大概的定義，當我們將一個 object 視為 rvalue 使用，使用的是此 object 的值 (contents)。當我們將一個 object 視為 lvalue 使用，使用的是此 object 的「存在」(記憶體位置)。還有一點也很重要，lvalue 可以代替 rvalue，但反之 rvalue 卻不能代替 lvalue。

      int a = 1;     // a = lvalue, 1 = rvalue
      int b = a + 1; // a = lvalue, a = rvalue (lvalue 代替 rvalue)
      int 1 = a;     // Error, 1 != lvalue (rvalue 不能代替 lvalue)
  

Operators

• Logical and Relational Operators

  Logical Operators 和 Relational Operators 回傳 bool。Logical Operators AND 跟 OR 永遠都會先計算左側再來計算右側。這裡想特別紀錄的是 && 跟 ||，&& 代表只有左側計算出來是 True 才會計算右側，|| 則是只有左側計算出來是 False 才會計算右側。這可以寫出一些流程控制而不是使用典型的 if else。Relational Operators 則是 >, <, >=, <=, ! 這些。

      // 以下這兩個 val 都會被轉換成 bool
      if (val)  { /*  ...  */ } // true if val is any nonzero value
      if (!val) { /*  ...  */ } // true if val is zero
  
      // 有了上面兩個例子，我們看似可以將其改寫成以下寫法
      if (val == true) { /*  ...  */ }
  
      // 這個會產生問題，只要 val 的型別不是 bool
      // 假設 val 是 int，true 會被轉換成 int 也就是 1 跟原先的任何 nonzero value 相去甚遠
      if (val == 1) { /*  ...  */ } // true if val is 1
  

• Assignment Operators

  最常見就是等號 (=)。Assignment 是 Right Associative，以下有程式碼示範。另外 Assignment Operators 執行順序較低通常會用括弧輔助。

      int ival, jval;
      ival = jval = 0; // ok: each assigned 0
      // 對於右邊的 assignment，jval = 0
      // 對於左邊的 assignment，ival = (jval = 0)
      // jval assigned 0 後，回傳 jval (ival = jval)，ival = 0
  

      // 原先邏輯
      int i = get_value();
      while (i != 42) {
          // do something ...
          i = get_value();
      }
      // 改寫，用括弧輔助
      int i;
      while ((i = get_value()) != 42) {
          // do something ...
      }
  

• Increment and Decrement Operators

  ++ -- 用來做 Increment 和 Decrement，兩個都有 prefix 跟 postfix 的寫法，效果如下程式碼示範。要注意的是要盡量用 prefix 來做運算，因為你通常不會需要做增減前的 value，而 postfix 會 copy 一份增減前的 value 來做回傳。 

      int i = 0, j;
      j = ++i; // j = 1, i = 1: prefix yields the incremented value
      j = i++; // j = 1, i = 2: postfix yields the unincremented value
  
      // 需要 postfix 的場合
      auto pbeg = v.begin();
      // print elements up to the first negative value
      while (pbeg != v.end() && *beg >= 0)
          cout << *pbeg++ << endl; // print the current value and advance pbeg
  

  Operand 運算順序不是固定的，通常不會造成問題，但如果兩邊有用到同一 variable 且用了 Increment 或 Decrement Operators 問題就會浮現。

      // 原先邏輯是把 s 裡的 char 都改成大寫
      // the behavior of the following loop is undefined!
      auto it = s.begin()
      while (it != s.end() && !isspace(*it))
          *it = toupper(*it++);   // error: this assignment is undefined
  
      // 會有兩種結果
      // 第一種輸出 ABCDEFG
      *beg = toupper(*beg);        // 先執行左邊的 Operand，Output: ABCDEFG
      *(beg + 1) = toupper(*beg);  // 先執行左邊的 Operand，Output: aAAAAAA
  

• Shift Operators (aka IO Operators) Are Left Associative

      cout << "hi" << " there" << endl;
      ( (cout << "hi") << " there" ) << endl;
  
      cout << 42 + 10;   // ok: + has higher precedence, so the sum is printed
      cout << (10 < 42); // ok: parentheses force intended grouping; prints 1
      cout << 10 < 42;   // error: attempt to compare cout to 42!
  

Read More