# 线段树

Leetcode307

## 1 线段树

``````class segTreeNode {
public:
segTreeNode(int start, int end, int val, segTreeNode* left = nullptr, segTreeNode* right = nullptr) : start(start), end(end), val(val), left(left), right(right) {}

~segTreeNode() {
delete left;
delete right;
left = right = nullptr;
}

int start;
int end;
int val;    // can be sum, min, max...
segTreeNode* left;
segTreeNode* right;
};``````

``````segTreeNode* buildTree(int start, int end, vector& nums) {
if (start == end)
return new segTreeNode(start, end, nums[start]);
int mid = (start + end) / 2;
auto left = buildTree(start, mid, nums);
auto right = buildTree(mid + 1, end, nums);
auto root = new segTreeNode(start, end, left->val + right->val, left, right);
return root;
}``````

``````void update(segTreeNode* root, int i, int newVal) {
if (root->start == i && root->end == i) {
root->val = newVal;
return;
}
int mid = root->start + (root->end - root->start) / 2;
if (i <= mid)
update(root->left, i, newVal);
else
update(root->right, i, newVal);
root->val = root->left->val + root->right->val;
}``````

1. 范围正好和根结点负责的范围一致，直接返回；
2. 范围由某个下层结点负责，找到该结点返回其值；
3. 范围由两个下层结点组合负责，返回两个结点的sum。

``````int query(segTreeNode* root, int i, int j) {
if (i == root->start && j == root->end)
return root->val;
int mid = root->start + (root->end - root->start) / 2;
if (j <= mid)  // 查询范围完全落在左子树
return query(root->left, i, j);
else if (i > mid)  // 查询范围完全落在右子树
return query(root->right, i, j);
else
return query(root->left, i, mid) + query(root->right, mid + 1, j);
}``````

## 2 Reference

• 花花酱 Segment Tree 线段树 SP14
• 一步一步理解线段树