hdu 1166 선분 트 리

http://acm.hdu.edu.cn/showproblem.php?pid=1166
제목:T 조 테스트,각 조 테스트 는 N 개의 공병 영 이 있 으 며,각 공병 영 의 초기 병사 수 를 제시 합 니 다.다음은 여러 가지 조작 이 있 습 니 다.
Add i j     i 와 j 는 정수 로 i 번 째 캠프 에 j 개인(j 가 30 을 초과 하지 않 음)을 증가 시 키 는 것 을 나타 낸다.Sub i j      i 와 j 는 정수 로 i 번 째 캠프 에서 j 개인(j 가 30 을 초과 하지 않 음)을 감소 하 는 것 을 나타 낸다.Query i j   i 와 j 는 정수 이 고 i<=j 는 i 에서 j 개 캠프 까지 의 총 인원 을 묻는다.End          끝 을 표시 합 니 다.이 명령 은 각 그룹의 데이터 마지막 에 나타 납 니 다.각 그룹의 데 이 터 는 최대 40000 개의 명령 이 있다.
사고:선분 수 를 만 들 고 각 점 에서 이 지역 의 병사 총 수 를 기록 합 니 다.

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define SIZE 50004
using namespace std;
struct node
{
	int sum,left,right;
}a[SIZE<<2];
int num[SIZE];
int Build(int left,int right,int root)
{
    int m;
    a[root].left=left;
    a[root].right=right;
    if(left==right){
         a[root].sum=num[right];
         return a[root].sum;
    }
    m=(right+left)>>1;
    a[root].sum=Build(left,m,root<<1);
    a[root].sum+=Build(m+1,right,root<<1|1);
    return a[root].sum;
}
void Add(int root,int x,int y)
{
    int m;
    a[root].sum+=y;
    if(a[root].left==a[root].right && a[root].left==x){
        return;
    }
    m=(a[root].right+a[root].left)>>1;
    if(x<=m){
        Add(root<<1,x,y);
    }
    else{
        Add(root<<1|1,x,y);
    }
    return;
}
int Query(int root,int left,int right)
{
    int sum=0;
    if(left<=a[root].left && right>=a[root].right){
        return a[root].sum;
    }
    if(a[root<<1].right>=right){
        sum+=Query(root<<1,left,right);
    }
    else if(a[root<<1|1].left<=left){
        sum+=Query(root<<1|1,left,right);
    }
    else{
        sum+=Query(root<<1,left,a[root<<1].right);
        sum+=Query(root<<1|1,a[root<<1|1].left,right);
    }
    return sum;
}
int main()
{
    int T,nCase=1,n,x,y,i,sum;
    char ope[10];
    scanf("%d",&T);
    while(T--){
		memset(a,0,sizeof(a));
        memset(num,0,sizeof(num));
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",&num[i]);
        }
        Build(1,n,1);
        printf("Case %d:
",nCase++);
        while(scanf("%s",ope),strcmp(ope,"End")!=0){
             scanf("%d%d",&x,&y);
             if(strcmp(ope,"Add")==0){
                 Add(1,x,y);
             }
             else if(strcmp(ope,"Sub")==0){
                 Add(1,x,-y);
             }
             else{
                 sum=Query(1,x,y);
                 printf("%d
",sum);
             }
        }
    }
    return 0;
}