HDU-1166-敌兵布阵

求区间的和，并可更新，线段树

[cpp] 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
#define N 50005 
int num[N]; 
struct cam 
{ 
    int x;  //起点 
    int y;  //终点 
    int sum; //总数 
}list[N*4]; 
void build(int k,int x,int y) 
{ 
    int mid; 
    list[k].x=x; 
    list[k].y=y; 
    if(list[k].x==list[k].y) 
    { 
        list[k].sum=num[x]; 
        return; 
    } 
    mid=(x+y)/2; 
    build(k<<1,x,mid); 
    build(k<<1|1,mid+1,y); 
    list[k].sum=list[k<<1].sum+list[k<<1|1].sum; 
} 
int find(int k,int x,int y) 
{ 
    int mid; 
    if(list[k].x==x&&list[k].y==y) 
    return list[k].sum; 
    mid=(list[k].x+list[k].y)/2; 
    if(x>mid) 
    return find(k<<1|1,x,y); 
    else if(y<=mid) 
    return find(k<<1,x,y); 
    return find(k<<1,x,mid)+find(k<<1|1,mid+1,y); 
} 
void update(int k,int x,int y) 
{ 
    int mid; 
    if(list[k].x==x&&list[k].y==x) 
    { 
        list[k].sum=y; 
        return; 
    } 
    mid=(list[k].x+list[k].y)/2; 
    if(x<=mid) 
    update(k<<1,x,y); 
    else 
    update(k<<1|1,x,y); 
    list[k].sum=list[k<<1].sum+list[k<<1|1].sum; 
}   www.2cto.com
int main() 
{ 
    int k,t,a,b; 
    int i,n,m; 
    char str[10]; 
    scanf("%d",&t); 
    for(k=1;k<=t;k++) 
    { 
        scanf("%d",&n); 
        for(i=1;i<=n;i++) 
        scanf("%d",&num[i]); 
        build(1,1,n); 
        printf("Case %d:/n",k); 
        while(scanf("%s",str),strcmp(str,"End")) 
        { 
            scanf("%d%d",&a,&b); 
            if(strcmp(str,"Query")==0) 
            printf("%d/n",find(1,a,b)); 
            else if(strcmp(str,"Add")==0) 
            { 
                num[a]+=b; 
                m=num[a]; 
                update(1,a,m); 
            } 
            else if(strcmp(str,"Sub")==0) 
            { 
                num[a]-=b; 
                m=num[a]; 
                update(1,a,m); 
            } 
        } 
    } 
    return 0; 
} 

 作者：Cambridgeacm