- 2022tysc0158 的博客
【模板】树状数组
- 2024-4-7 20:32:28 @
#include<cstdio>
#define lowbit(x) (x&(-x))
int n,m,opt,x,y,tree[500001];
void add(int x,int d){//将第 x 个数加上 d
while(x<=n){
tree[x]+=d;
x+=lowbit(x);
}
}
int query(int x){// 查询前 x 个数的总和
int sum=0;
while(x){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
add(i,x);
}
while(m--){
scanf("%d%d%d",&opt,&x,&y);
if(opt==1)add(x,y);
else printf("%d\n",query(y)-query(x-1));
}
}