HDU1166 敌兵布阵（线段树模板）

#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
struct node{
    int l,r;
    int cnt;
}tr[N*4];
int a[N];
void pushup(int u){
    tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;
}
void build(int u,int l,int r){
    if(l==r){
        tr[u]=node{l,l,a[l]};
    }
    else{
        int mid=l+r>>1;
        tr[u]=node{l,r};
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int x,int y){
    if(tr[u].l==tr[u].r){
        tr[u].cnt+=y;
        return ;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid)
        modify(u<<1,x,y);
    else
        modify(u<<1|1,x,y);
    pushup(u);
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].cnt;
    }
    int mid=tr[u].l+tr[u].r>>1;
    int res=0;
    if(l<=mid)
        res=query(u<<1,l,r);
    if(r>mid)
        res+=query(u<<1|1,l,r);
    return res;
}
int main(){
    int n,m;
    int t;
    cin>>t;
    int cnt=1;
    while(t--){
        cin>>n;
        int i;
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1,1,n);
        string s;
        printf("Case %d:\n",cnt++);
        while(cin>>s){
            if(s=="End")
                break;
            if(s=="Add"){
                int x;
                int y;
                scanf("%d%d",&x,&y);
                modify(1,x,y);
            }
            else if(s=="Sub"){
                int x;
                int y;
                scanf("%d%d",&x,&y);
                modify(1,x,-y);
            }
            else{
                int x,y;
                scanf("%d%d",&x,&y);
                printf("%d\n",query(1,x,y));
            }
        }
    }
    return 0;
}