hdu 1166敵兵布陣樹状配列

1行目の整数Tは、Tグループのデータがあることを示す.各組のデータの第1行には正の整数N(N<=50000)があり、敵にはN個の工兵キャンプがあり、次にN個の正の整数aiがあり、第i個の正の整数aiは第i個の工兵キャンプの開始時にai人(1<=ai<=50)があることを示す.次に各行には命令があり、命令は4つの形式がある:(1)Add i j,i,jは正の整数であり、第i個のキャンプにj人(jが30を超えない)(2)Subi jを増加することを示す.iとjは正の整数であり、i番目のキャンプがj個人を減らすことを示す(jは30を超えない);(3)Query i j,iとjは正の整数であり、i<=jであり、i番目からj番目のキャンプに尋ねる総人数を示す.
(4)Endは終了を示し、このコマンドは各グループのデータの最後に現れる.
やはりクエリーと更新操作、ツリー配列~

#include
#include
#include
int c[50005];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void modify(int i,int j)//  
{
    while(i<=n)
    {
        c[i]+=j;
        i=i+lowbit(i);
    }
}
long long sum(int i)//  
{
    long long s=0;
    while(i>0)
    {
        s+=c[i];
        i=i-lowbit(i);
    }
    return s;
}
int main()
{
    int T,a;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        memset(c,0,sizeof(c));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            modify(i,a);
        }
        char str[10];
        scanf("%s",str);
        printf("Case %d:
",t);
        while(strcmp(str,"End")!=0)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(strcmp(str,"Query")==0)
                printf("%lld
",sum(y)-sum(x-1));
            else if(strcmp(str,"Add")==0)
                modify(x,y);
            else if(strcmp(str,"Sub")==0)
                modify(x,(-1)*y);
            scanf("%s",str);
        }
    }
}