题目大意
维护一个长度为 n 的数组，支持两类操作：
1）单点加上一个值。
2）查询区间 [l,r] 的元素和。
似乎这题也可以用树状数组解决
https://zh.wikipedia.org/wiki/二補數
lowbit()原理详见这里
视频教程
https://www.bilibili.com/video/BV1ce411u7qP/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675
区间和我们实际上是用两前缀和相减得到的
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
35
36
37
38
39
40
41
42
43
| #include <iostream>
using namespace std;
const int maxn=5e5+10;
int n,m,tr[maxn],sumTr[maxn],x,y,k,op;
inline int lowbit(int x){
return (x&(-x));
}
inline void add(int p,int v){
while(p<n+1){
tr[p]+=v;
p+=lowbit(p);
}
}
int search(int p){
if(p==0) return 0;
return search(p-lowbit(p))+tr[p];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>tr[i];
}
for(int i=1;i<=n;i++){
sumTr[i]=tr[i]+sumTr[i-1];
}
for(int i=1;i<=n;i++){
tr[i]=sumTr[i]-sumTr[i-lowbit(i)];
}
for(int _=1;_<=m;_++){
cin>>op;
if(op==1){
cin>>x>>k;
add(x,k);
}else{
cin>>x>>y;
int ans=search(y)-search(x-1);
cout<<ans<<endl;
}
}
}
|