动态求连续区间和_线段树

https://www.acwing.com/problem/content/1266/

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct Node{
    int l,r;
    int sum;
}tr[N*4];
int w[N];
int m,n;
void pushup(int x){
    tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;//向上更新
}
void build(int x,int l,int r){//节点编号 左端点 右端点
    if(l==r){                   //如果当前区间只有一个节点 
        tr[x]={l,r,w[l]};

    }
    else{
        tr[x]={l,r};
        int mid=l+r>>1;
        build(x<<1,l,mid);//构建左儿子
        build(x<<1|1,mid+1,r);//构建右儿子
        pushup(x);
    }
}
void modify(int x,int u,int v){//节点编号 目标 更新值
    if(u==tr[x].l&&u==tr[x].r){//当前节点是目标节点
        tr[x].sum+=v;
        return;
    }
    int mid=tr[x].l+tr[x].r>>1;

    if(u<=mid)modify(x<<1,u,v);//如果目标节点在左儿子
    else modify(x<<1|1,u,v);//如果目标节点在右儿子
    pushup(x);
}
int q(int x,int l,int r){//节点编号 查询左端点 查询右端点
    if(l<=tr[x].l&&r>=tr[x].r)return tr[x].sum;//如果查询区间包含当前区间
    int sum=0;
    int mid=tr[x].r+tr[x].l>>1;
    if(l<=mid)sum+=q(x<<1,l,r);//查询区间与当前区间左儿子存在交集
    if(r>mid)sum+=q(x<<1|1,l,r);//查询区间与当前区间右儿子存在交集
    return sum;//返回区间和
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    build(1,1,n);
    while(m--){
        int k,a,b;
        scanf("%d%d%d",&k,&a,&b);
        if(k==0){
            printf("%d\n",q(1,a,b));
            continue;
        }
        modify(1,a,b);
    }

     return 0;
}