树状数组模板
2026-08-04 09:55:16
发布于：浙江
24阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[500010],tree[500010]; //tree[i] = a[i-lowbit(i)+1,i] 的和
int lowbit(int x){
return x&-x;
}
void add(int x,int y){
//找父亲操作，给每个父亲全部加上 y
//i 的父亲是 i+lowbit(i)，即让 i 进位
for(;x<=n;x+=lowbit(x)){
tree[x]+=y;
}
}
//[1,x] 区间的和
long long ask(long long x){
//从后往前累加
long long sum=0;
for(;x;x-=lowbit(x))sum+=tree[x];
return sum;
}
void solve(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);
}
while(q--){
int op,l,r;
cin>>op>>l>>r;
if(op==1)add(l,r);
else {
cout<<ask(r)-ask(l-1)<<endl;
}
}
}
int main(){
solve();
}
有帮助，赞一个