题目描述

给定一个整数数组 nums，求 i 到 j (i <= j) 的区间和。

update(i, val)操作每次回修改i位置的元素为 val。

样例

给定 nums = [1, 3, 5]

求和(0, 2) -> 9
update(1, 2)
求和(0, 2) -> 8

提示

• 数组仅可以在 update 函数下进行修改。
• 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

算法

(树状数组) $O(n + Q \log n)$

1. 树状数组模板题，树状数组是特殊的前缀和数组，可以维护原数组每次变化的增量。
2. 树状数组在每次修改时，并不总是修改 i 之后的所有点，而是根据 lowbit 操作依次向后修改影响到的点。
3. 同样，在查询时，也是根据 lowbit 序列向前统计前缀和，两次前缀和的差值就是区间和。
4. 注意，树状数组的下标必须从 1 开始。
5. 对于此题，由于题目每次是更新值，并不是更新增量，故需要用原数组记录每次更新后的点的值。
6. 为了节约初始化的时间，仍需要一个普通前缀和数组记录初始数组的每个点的前缀和，树状数组用来维护修改增量的前缀和。

时间复杂度

• 初始化时间复杂度为 $O(n)$，每次更新或查询操作的时间复杂度为 $O(\log n)$，故总时间复杂度为 $O(n + Q \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储树状数组和前缀和数组。

C++ 代码

class NumArray {
public:
    vector<int> a, f, sum;
    int n;
    NumArray(vector<int> nums) {
        n = nums.size();
        a = nums;
        f = vector<int>(n + 1, 0);
        sum = vector<int>(n + 1, 0);
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + nums[i - 1];
    }

    void update(int i, int val) {
        int x = i;
        for (x++; x <= n; x += x & -x)
            f[x] += val - a[i];
        a[i] = val;
    }

    int prefixSum(int x) {
        int res = 0;
        for (; x; x -= x & -x)
            res += f[x];
        return res;
    }

    int sumRange(int i, int j) {
        return prefixSum(j + 1) - prefixSum(i) + sum[j + 1] - sum[i];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */