线段树

针对力扣307题，找到题解 https://leetcode.cn/problems/range-sum-query-mutable/solution/by-lfool-v3x9/

线段树解决的是「区间和」的问题，且该「区间」会被修改

所以线段树主要实现两个方法：「求区间和」&&「修改区间」，且时间复杂度均为 O(logn)

始终记住一句话：线段树的每个节点代表一个区间

从图中可以看到，每个节点代表一个区间，而节点的值就是该区间的和 (其实还可以根据题目问题，改变表示的含义！！)

数字之和「总数字之和 = 左区间数字之和 + 右区间数字之和」
最大公因数 (GCD)「总 GCD = gcd(左区间 GCD, 右区间 GCD)」
最大值「总最大值 = max(左区间最大值，右区间最大值)」

不符合区间加法的例子：

• 众数「只知道左右区间的众数，没法求总区间的众数」
• 01 序列的最长连续零「只知道左右区间的最长连续零，没法知道总的最长连续零」

---

class NumArray {
private:
    vector<int> segmentTree;
    int n;

    void build(int node, int start, int end, vector<int> &nums) {
        if (start == end) {
            segmentTree[node] = nums[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(node * 2 + 1, start, mid, nums);
        build(node * 2 + 2, mid + 1, end, nums);
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
    }

    void change(int index, int val, int node, int start, int end) {
        if (start == end) {
            segmentTree[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        if (index <= mid) {
            change(index, val, node * 2 + 1, start, mid);
        } else {
            change(index, val, node * 2 + 2, mid + 1, end);
        }
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
    }

    int range(int left, int right, int node, int start, int end) {
        if (left == start && right == end) {
            return segmentTree[node];
        }
        int mid = start + (end - start) / 2;
        if (right <= mid) {
            return range(left, right, node * 2 + 1, start, mid);
        } else if (left > mid) {
            return range(left, right, node * 2 + 2, mid + 1, end);
        } else {
            return range(left, mid, node * 2 + 1, start, mid) + range(mid + 1, right, node * 2 + 2, mid + 1, end);
        }
    }

public:
    NumArray(vector<int>& nums) : n(nums.size()), segmentTree(nums.size() * 4) {
        build(0, 0, n - 1, nums);
    }

    void update(int index, int val) {
        change(index, val, 0, 0, n - 1);
    }

    int sumRange(int left, int right) {
        return range(left, right, 0, 0, n - 1);
    }
};
 

针对力扣307题的题解 https://leetcode.cn/problems/range-sum-query-mutable/solution/by-lfool-v3x9/

• 对于表示为「区间和」且对区间进行「加减」的更新操作的情况，我们在更新节点值的时候『需要✖️左右孩子区间叶子节点的数量 (注意是叶子节点的数量)』；我们在下推懒惰标记的时候『需要累加』！！(这种情况和模版一致！！) 如题目 最近的请求次数
• 对于表示为「区间和」且对区间进行「覆盖」的更新操作的情况，我们在更新节点值的时候『需要✖️左右孩子区间叶子节点的数量 (注意是叶子节点的数量)』；我们在下推懒惰标记的时候『不需要累加』！！(因为是覆盖操作！！) 如题目 区域和检索 - 数组可修改
• 对于表示为「区间最值」且对区间进行「加减」的更新操作的情况，我们在更新节点值的时候『不需要✖️左右孩子区间叶子节点的数量 (注意是叶子节点的数量)』；我们在下推懒惰标记的时候『需要累加』！！ 如题目 我的日程安排表 I、我的日程安排表 III

。