学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

题目意思，就是树状数组的定义几乎一样。

值的注意的是，该题目的输入量比较大，第一次采用cin作为输入，TLE了，改用scanf就过了，时间达到了700ms+。

作为练习树状数组的题目吧，熟悉下树状数组。当然这题还可以用线段树来做，但是，代码有点长，还是不太好。

代码：

//freopen("C:\\Documents and Settings\\All Users\\×ÀÃæ\\in.txt","r",stdin);

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<map>

using namespace std;

int C[50010];
int n;

int lowbit(int x){return x&-x;}

int sum(int x){
    int ret=0;
    while(x>0){ret+=C[x];x-=lowbit(x);}
    return ret;
}

void add(int x,int d){
    while(x<=n){C[x]+=d;x+=lowbit(x);}
}

int main(){
    //freopen("C:\\Documents and Settings\\All Users\\×ÀÃæ\\in.txt","r",stdin);
    int T;cin>>T;
    for(int cas=1;cas<=T;cas++)
    {
        printf("Case %d:\n",cas);
        memset(C,0,sizeof(C));
        cin>>n;
        for(int i=1;i<=n;i++){
            int t;scanf("%d",&t);
            add(i,t);
        }
        char s[10];
        while(scanf("%s",s)){
            if(s[0]=='E') break;
            int l,r;
            cin>>l>>r;
            if(s[0]=='Q'){
                l=sum(l-1);r=sum(r);
                cout<<(r-l)<<endl;
            }else{
                int op;
                s[0]=='A'? op=1:op=-1;
                add(l,r*op);
            }
        }
    }

    return 0;
}