307. 区域和检索 - 数组可修改（zkw线段树单点修改区间查询） · znzryb

## 思路讲解

参考题解以及视频讲解

【数据结构扩展(二) --线段树 (普通+zkw)】 【精准空降到 18:48】 [https://www.bilibili.com/video/BV1gy4y1D7dx/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1128](https://www.bilibili.com/video/BV1gy4y1D7dx/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1128)

[https://www.cnblogs.com/Judge/p/9514862.html](https://www.cnblogs.com/Judge/p/9514862.html)

![image](https://media.znzryb.com/20250404-796a1d3b/image_05be184c.png)

## AC代码

[https://leetcode.cn/problems/range-sum-query-mutable/submissions/618952189](https://leetcode.cn/problems/range-sum-query-mutable/submissions/618952189)

```cpp
class NumArray {
public:
    typedef long long ll;
    vector<ll> tree;
    ll N;
    void update(int index, int val) {
        ll diff=val-tree[index+N];
        for(int i=index+N;i>0;i>>=1){
            tree[i]+=diff;
        }
    }
    int sumRange(int left, int right) {
        ll res=0;
        for(int i=left+N,j=right+N;i<=j;i>>=1,j>>=1){
            if(i%2==1) res+=tree[i++];
            if(j%2==0) res+=tree[j--];
        }
        return res;
    }
    NumArray(vector<int>& nums) {
        // for(int i=0;i<nums.size();++i){
        //     lnum.push_back(nums[i]);
        // }
        N=nums.size();
        tree.resize(2*N+5,0);
        for(int i=0;i<nums.size();++i){
            update(i,nums[i]);
        }
        // for(int i=0;i<tree.size();++i){
        //     cout<<i<<": "<<tree[i]<<"\n";
        // }
    }
    
};
```

## 心路历程（WA，TLE，MLE……）