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