hdu 1166 敌兵布阵（简单线段树or树状数组）

浏览数：31 / 时间：2015年06月08日

题意：

N个工兵营地，第i个营地有ai个人。

三种操作：

1.第i个营地增加x个人。

2.第i个营地减少x个人。

3.查询第i个到第j个营地的总人数。

思路：

线段树or树状数组

代码：(树状数组)

int n;
int a[50005];
int C[50005];

void init(){
    rep(i,1,n){
        C[i]=0;
        for(int j=i-lowbit(i)+1;j<=i;j++){
                C[i]+=a[j];
        }
    }
}
void add(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i)){
        C[i]+=y;
    }
}

int calc(int x){
    if(x==0) return 0;
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans+=C[i];
    return ans;
}
int query(int x,int y){
    return calc(y)-calc(x-1);
}

int main(){

    int T;
    cin>>T;
    rep(t,1,T){
        scanf("%d",&n);
        rep(i,1,n){
            scanf("%d",&a[i]);
        }

        init();

        printf("Case %d:\n",t);

        char ope[10];
        while(1){
            scanf("%s",ope);
            if(ope[0]==‘E‘) break;
            int x,y;
            if(ope[0]==‘A‘){
                scanf("%d%d",&x,&y);
                add(x,y);
            }
            else if(ope[0]==‘S‘){
                scanf("%d%d",&x,&y);
                add(x,-y);
            }
            else{
                scanf("%d%d",&x,&y);
                int ans=query(x,y);
                printf("%d\n",ans);
            }
        }
    }

    return 0;
}