树状数组 hdoj1166

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

度娘的 树状数组 http://baike.baidu.com/view/1420784.htm 弄了一个下午，算是明白了点

看了一些牛人的代码后的翻版。。

#include<iostream>
using namespace std;
int tr[500005],n;
int lowbit(int a){return a&-a;}//找位置 
int quy(int i) //计算前i项和 
{
    int ans=0;
    for(;i>0;i-=lowbit(i))
       ans+=tr[i];
       return ans;
}
void modify(int i,int j)  //改变的值 
{
    for(i;i<=n;i+=lowbit(i)) tr[i]+=j;
}
int main()
{
//    freopen("in.txt","r",stdin);
    int t,a;
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        memset(tr,0,sizeof(tr));
        int one,two,i;
        char s[10];
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a);
            modify(i,a);//建树 
        //    tr[i]+=tr[i-1];
        }
    //    for(i=n;i>=1;i--) tr[i]-=tr[i-lowbit(i)]; //建树 
        printf("Case %d:\n",k);
        while ( scanf("%s",s),s[0]!='E')
        { 
            scanf("%d%d",&one,&two);
            if(s[0]=='Q')
            {
                printf("%d\n",quy(two)-quy(one-1));
            }
            else if(s[0]=='A') modify(one,two); 
            else modify(one,-two);
        }
    }
    return 0;
}