acwing1264. 动态求连续区间和

题目

题解

• 树状数组
  c[x]=tree[x-lowbit(x),x]:c[x]的和可以由tree[x-lowbit(x)]到tree[x]的和表示

#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int q[N],tree[N];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)){
        tree[i]+=c;
    }
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tree[i];
    return res;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&q[i]);
   for(int i=1;i<=n;i++)
        add(i,q[i]);
    while(m--){
        int k,a,b;
        cin>>k>>a>>b;
        if(k==0){
            cout<<query(b)-query(a-1)<<endl;
        }else {
            add(a,b);
        }
    }
    
    return 0;
}