题解 | A22721.【模板】树状数组

还是老老实实用树状数组做吧

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
struct node{
    int l,r,sum;
}tr[N*4];
int n,m,a[N];
//在递归回溯的时候，通过子节点信息更新父节点信息

void pushup(int u){
    tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}
void build(int u,int l,int r){ //构建线段树build
        tr[u]={l,r};
        if(l==r){
            tr[u].sum=a[l];
            return;
        }
        int mid=(l+r)/2;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
}
void modify(int u,int pos,int k){ //单点修改操作，将第pos个数字加上
        if(tr[u].l==tr[u].r){ //找到了
            tr[u].sum+=k; 
            return;
        }
        int mid=(tr[u].l+tr[u].r)/2;
        if(pos<=mid) modify(u*2,pos,k);
        else modify(u*2+1,pos,k);
        pushup(u);
}
int query(int u,int l,int r){ //查询区间[l,r]的和
        if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
        int mid=(tr[u].l+tr[u].r)/2;
        int ans=0;
        if(l<=mid)ans+=query(u*2,l,r);
        if(r>mid)ans+=query(u*2+1,l,r);
        return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);

    while(m--){
        int op;cin>>op;
        if(op==1){
            int x,k;cin>>x>>k;
            modify(1,x,k);
        }else{
            int x,y;cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }
}