思路讲解
参考题解以及视频讲解
【数据结构扩展(二) --线段树 (普通+zkw)】 【精准空降到 18:48】 https://www.bilibili.com/video/BV1gy4y1D7dx/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1128
https://www.cnblogs.com/Judge/p/9514862.html
AC代码
https://leetcode.cn/problems/range-sum-query-mutable/submissions/618952189
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| 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) {
N=nums.size();
tree.resize(2*N+5,0);
for(int i=0;i<nums.size();++i){
update(i,nums[i]);
}
}
};
|
心路历程（WA，TLE，MLE……）