zkw.cpp

//http://acm.hdu.edu.cn/showproblem.php?pid=1166
#include <iostream>
#include <stdio.h>
#include <string.h>
#define N 50005
using namespace std;

int M;
int T[N*4];
int Query(int s,int t){
    int ans=0;
    for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
        if(~s&1) ans+=T[s^1];
        if( t&1) ans+=T[t^1];
    }
    return ans;
}
void Add(int n,int V){
    for(T[n+=M]+=V,n>>=1;n;n>>=1){
        T[n]=T[n+n]+T[n+n+1];
    }
}
void build_tree(int n){
    int i;
    for(M=1;M<=n+1;M*=2){}
    //for(i=M+1;i<=M+n;i++){
    //    scanf("%d",&T[i]);
    //}
    //for(i=M-1;i>0;i--) T[i]=T[i*2]+T[i*2+1];//求解这里读入肿么了- -就是不让过
}

int main()
{
    int t,n,a,b,k=0;
    char str[10];
    scanf("%d",&t);
    while(t--){
        printf("Case %d:\n",++k);
        memset(T,0,sizeof(T));
        scanf("%d",&n);
        build_tree(n);
        for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        Add(i,x);
        }//硬是把读入搬到这- -  然后过了
        while(1){
            scanf("%s",str);
            if(strcmp(str,"Query")==0){//C&C++字符串什么的最讨厌了
                scanf("%d%d",&a,&b);
                cout << Query(a,b) << endl;
            }
            else if(strcmp(str,"Add")==0){
                scanf("%d%d",&a,&b);
                Add(a,b);
            }
            else if(strcmp(str,"Sub")==0){
                scanf("%d%d",&a,&b);
                Add(a,-b);
            }
            else if(strcmp(str,"End")==0){
                break;
            }
        }
    }
}