Problem: 307. 区域和检索 - 数组可修改

思路：

树状数组动态维护关键区间

Code

c++

class NumArray {
public:
    // 树状数组，存储每个关键区,长度即为nums数组的长度
    // 下标1开始算
    vector<int> tree;
    // 原数组
    vector<int> nums;
    int n;
    // 初始化tree和nums
    NumArray(vector<int>& nums) : tree((int)1e5,0), nums(nums),n(nums.size()) {
        //初始化树状数组
        for (int i = 0; i < nums.size(); i++) {
            int curr = i+1;
            tree[curr] += nums[i];
            if(curr+lowbit(curr)<=n)
            tree[curr+lowbit(curr)] += tree[curr]; 
        }
    }
    int lowbit(int i){
        return i&-i;
    }
    // 更新树状数组
    void update(int index, int val) {
        int deta = val - nums[index];
        //记得更新原数组！！！
        nums[index] = val;
        for(int i = index+1;i<=n;i+=lowbit(i)){
            tree[i]+=deta;
        }
    }
    // 求区间和
    int preSum(int idx){
        int s = 0;
        for(int i=idx;i>0;i-=lowbit(i)){
            s+=tree[i];
        }
        return s;
    }
    int sumRange(int left, int right) {
        return preSum(right+1)-preSum(left);
    }
};