hdu 1166 敌兵布阵_线段树

题意：略

思路：这题是单点更新，如果是减少的话，直接把数据变成负加上去就行了。

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 50010
int n,ans;
struct{
    int l,r,value;
}tree[MAXN<<2];
void Build(int l,int r,int id){
    tree[id].l=l;
    tree[id].r=r;
    tree[id].value=0;
    if(l!=r){
        int mid=(l+r)>>1;
        Build(l,mid,id<<1);
        Build(mid+1,r,id<<1|1);
    }
}
void update(int l,int value,int id){
    if(tree[id].l==tree[id].r&&tree[id].l==l){
        tree[id].value+=value;
        return;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(l<=mid)
        update(l,value,id<<1);
    else
        update(l,value,id<<1|1);
    tree[id].value=tree[id<<1].value+tree[id<<1|1].value;
}
void query(int l,int r,int id){
    if(tree[id].l==l&&tree[id].r==r){
        ans+=tree[id].value;
        return;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(r<=mid)
        query(l,r,id<<1);
    else if(l>mid)
        query(l,r,id<<1|1);
    else{
        query(l,mid,id<<1);
        query(mid+1,r,id<<1|1);
    }
}
int main(int argc, char** argv) {
    int Cas=1,t,x,y,n,i,value;
    char str[20];
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        Build(1,n,1);
        for(i=1;i<=n;i++){
            scanf("%d",&value);
            update(i,value,1);
        }
        printf("Case %d:\n",Cas++);
        while(scanf("%s",str),strcmp(str,"End")){
            scanf("%d%d",&x,&y);
            if(strcmp(str,"Add")==0)update(x,y,1);
            else if(strcmp(str,"Sub")==0)update(x,-y,1);
            else{
                ans=0;
                query(x,y,1);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

hdu 1166 敌兵布阵_线段树

原文：http://blog.csdn.net/neng18/article/details/19631387