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 中文講解