算法1

思路：树状数组

树状数组一般应用在“单点修改，区间压缩”，即在某个位置加上某个数，或者求一个前缀和

C++ 代码

#include<iostream>
#include<cstdio>

using namespace std;
const int N=100010;

int n,m;

int a[N],tr[N];
//树状数组的三个操作，lowbit,在某一位置加上一个数，求和，最好背过
int lowbit(int x){
    return x&-x;

} 
void add(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i))
    tr[i]+=v;

}

int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main(){
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)scanf("%d",&a[i]);
   for(int i=1;i<=n;i++)add(i,a[i]);

    while(m--){
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);

        if(k==0)printf("%d\n",query(y)-query(x-1));
        else{
            add(x,y);
        }

    }
    return 0;
}

算法2

线段树做法

#include<iostream>
#include<cstdio>

using namespace std;

const int N=1000010;

int n,m;
int w[N];

struct Node{
    int l,r;
    int sum;
}tr[N*4];//节点个数会开四倍的N

void pushup(int u){//pushup函数用于写当前节点的信息，即左右儿子的和

    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;

}
void build(int u,int l,int r){

    if(l==r)tr[u]={l,r,w[r]};//如果只有一个节点
    else{
        tr[u]={l,r};//赋初值
        int mid=l+r>>1;//mid取中间值
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);//遍历左右孩子
        pushup(u);//pushup相当于回溯
    }


}

int query(int u,int l,int r){

    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
    int mid=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=mid) sum=query(u<<1,l,r);
    if(r>mid)sum+=query(u<<1|1,l,r);
    return sum;

}

void modify(int u,int x,int v){

    if(tr[u].l==tr[u].r) tr[u].sum+=v;
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);//修改完更新
    }
}

int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);

    build(1,1,n);//根节点是1，初试区间是1-n

    int k,a,b;
    while(m--){

        scanf("%d%d%d",&k,&a,&b);
        if(k==0)printf("%d\n",query(1,a,b));//query查询,第一个参数是根节点，第二三个位置是查询区间
        else modify(1,a,b);//修改，根节点编号，插入位置，修改的值

    }

    return 0;
}