敌兵布阵

#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 50001
//int c[maxn]; 
int a[4*maxn];
int sum[4*maxn];
void build(int rt,int l,int r){
    if (l==r) {
    	sum[rt]=a[l];return;
	}
    int m=(l+r)>>1;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    
}

void update(int pos,int val,int rt,int l,int r){
   if (l==r) {
		sum[rt]=sum[rt]+val;
		return;
	}
	int m=(l+r)>>1;
   if (pos<=m)
     update(pos,val,rt<<1,l,m);
   else update(pos,val,rt<<1|1,m+1,r);
   sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 
}

int query(int L,int R,int rt,int l,int r)
{
	if (L<=l&&r<=R) return sum[rt];
    int m=(l+r)>>1;
     int ans=0;
	if (L<=m)
    ans+=query(L,R,rt<<1,l,m);
    if (R>m)
    ans+=query(L,R,rt<<1|1,m+1,r);
    return ans;
}

int main()
{   char s[100];int T;int n;
	scanf("%d",&T);
	for (int kase=1;kase<=T;kase++){
	
		memset(a,0,sizeof(a));
		memset(sum,0,sizeof(sum));
		scanf("%d",&n);
		printf("Case %d:\n",kase);
		for (int i=1;i<=n;i++)
		    scanf("%d",&a[i]);
		
		build(1,1,n); 
		while (~scanf("%s",s)&&strcmp(s,"End")!=0){
			int x,y;
			scanf("%d%d",&x,&y);
			if (s[0]=='Q') {
		       printf("%d\n",query(x,y,1,1,n));
			}
			else {
				if (s[0]=='S') 
				    update(x,-y,1,1,n);
			   else if(s[0]=='A')
			        update(x,y,1,1,n);
			}
		}
	}
}