HDU 1166

#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<math.h>
#include<set>
#include<stdlib.h>
#include<algorithm>
#define N 50005
using namespace std;
int num[N];
struct Tree{
    int l;
    int r;
    int sum;
}tree[N*4];    //总线段的长度为n，若开数组，一般开到n的4倍
void bulid(int root,int l,int r){
   // cout<<root<<" "<<l<<" "<<r<<endl;
    tree[root].l=l;
    tree[root].r=r;
    if(tree[root].l==tree[root].r){
        tree[root].sum=num[l];
        return;
    }
    int mid=(l+r)/2;
    bulid(root<<1,l,mid);
    bulid(root<<1|1,mid+1,r);
   tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}
void update(int root,int pos,int val){  //root 是根节点，将pos点的位置更新为val
    if(tree[root].l==tree[root].r){
        tree[root].sum=val;
        return;
    }
    int mid=(tree[root].l+tree[root].r)/2;
    if(pos<=mid){
        update(root*2,pos,val);
    }else
    update(root*2+1,pos,val);
    tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}
int query(int root,int L,int R){
    if(L<=tree[root].l&&R>=tree[root].r){
      //      cout<<root<<endl;
        return tree[root].sum;
    }
    int mid=(tree[root].l+tree[root].r)/2,ret=0;
    if(L<=mid) ret+=query(root*2,L,R);
    if(R>mid)  ret+=query(root*2+1,L,R);
    return ret;

}
 int main(){
    int n,t,a,b;
    char str[10];
   scanf("%d",&t);
    for(int k=1;k<=t;k++){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
          scanf("%d",&num[i]);
        bulid(1,1,n);
        printf("Case %d:\n",k);
        while(scanf("%s",str)){
            if(strcmp(str,"End")==0) break;
           scanf("%d%d",&a,&b);
            if(strcmp(str,"Query")==0){
                if(a>b) swap(a,b);
              printf("%d\n",query(1,a,b));
            }else if(strcmp(str,"Add")==0){
                num[a]+=b;
                update(1,a,num[a]);
            }else if(strcmp(str,"Sub")==0){
                num[a]-=b;
                update(1,a,num[a]);
            }
        }
    }
  return 0;
}