HDU 1166 敵兵布陣

分析：線段樹模板、學的時候畫圖分析、盡量不要看別人的模板、自己去分析、懂了原理然後自己把它寫出來相當有成就感、其實也就是創建、更新和查詢操作而已、說難也不難、

 
#include<stdio.h>  
#define N 50005  
struct node{  
    int l,r;  
    int sum;  
}tree[N<<2];  
int a[N];  
int ans,n;  
void create(int x,int l,int r){  
    tree[x].l=l;  
    tree[x].r=r;  
    if(l==r){  
        tree[x].sum=a[l];  
        return;  
    }  
    int mid=(l+r)/2;  
    create(x*2,l,mid);  
    create(x*2+1,mid+1,r);  
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;  
}  
void update(int x,int p,int num){  
    int l=tree[x].l;  
    int r=tree[x].r;  
    int mid=(l+r)/2;  
    if(l==r){  
        tree[x].sum+=num;  
        return;  
    }  
    if(p<=mid)  
        update(x*2,p,num);  
    else  
        update(x*2+1,p,num);  
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;  
}  
void query(int x,int l,int r){  
    if(tree[x].l==l&&tree[x].r==r){  
        ans+=tree[x].sum;  
        return;  
    }  
    int mid=(tree[x].l+tree[x].r)/2;  
    if(r<=mid)  
        query(x*2,l,r);  
    else if(l>mid)  
        query(x*2+1,l,r);  
    else{  
        query(x*2,l,mid);  
        query(x*2+1,mid+1,r);  
    }  
}  
int main(){  
    int t,x,y,k=1;  
    char str[10];  
    scanf("%d",&t);  
    while(t--){  
        printf("Case %d:\n",k);k++;  
        scanf("%d",&n);  
        for(int i=1;i<=n;i++)  
            scanf("%d",&a[i]);  
        create(1,1,n);  
        while(scanf("%s",str)){  
            if(str[0]=='E')break;  
            if(str[0]=='A'){  
                scanf("%d%d",&x,&y);  
                update(1,x,y);  
            }  
            if(str[0]=='S'){  
                scanf("%d%d",&x,&y);  
                update(1,x,-y);  
            }  
            if(str[0]=='Q'){  
                ans=0;  
                scanf("%d%d",&x,&y);  
                query(1,x,y);  
                printf("%d\n",ans);  
            }  
        }  
    }  
    return 0;  
}