[HDU][1166][树状数组] 敌兵布阵

题目大意：

给出一个序列和四种操作： (1) Add i j ，i和j为正整数，第i个元素增加j（j不超过30）； (2) Sub i j ，i和j为正整数，第i个元素减少j（j不超过30）； (3) Query i j ，i和j为正整数，i<=j，表示询问第i到第j个元素的和； (4) End 表示结束，这条命令在每组数据最后出现； 执行操作并对(3)进行答复。

思路：

树状数组、线段树的模板题。

代码：

#include
#include
using namespace std;
#define datasize 50000
int c[datasize+1],n;
int lowbit(int x)
{
    return x&-x;
}
int sum(int end)
//求取序列1至end的和。 
{
    int s=0;
    while(end>0)
    {
        s+=c[end];
        end-=lowbit(end);
    }
    return s;
}
void modify(int pos,int val)
//在序列第pos位上加上val。 
{
    while(pos<=n)
    {
        c[pos]+=val;
        pos+=lowbit(pos);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        printf("Case %d:\n",i);
        memset(c,0,sizeof(c));
        scanf("%d",&n);
        for(int j=1,t;j<=n;j++)
        {
            scanf("%d",&t);
            modify(j,t);
            //更新操作即是建树操作。 
        }
        char op[10];
        while(scanf("%s",op)&&strcmp(op,"End"))
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(!strcmp(op,"Query"))
                printf("%d\n",sum(b)-sum(a-1));
                //[a,b]的和即是[1,b]的和减去[1,a-1]的和。 
            else if(!strcmp(op,"Add"))
                modify(a,b);
            else if(!strcmp(op,"Sub"))
                modify(a,-b);
            else
                break;
        }
    }
}