1. 깊이가 k이고 2^(k-1)-1개의 결점이 있는 두 갈래 나무를 만 두 갈래 나무라고 부른다.
2. 두 갈래 나무의 깊이를 h로 설정하면 h층을 제외한 다른 각 층(1~h-1)의 결점은 최대 개수에 달하고 h층의 모든 결점은 연속적으로 맨 왼쪽에 집중된다. 이것이 바로 완전 두 갈래 나무다.완전 두 갈래 나무는 두 갈래 나무로 가득 차서 끌어낸 것이다.깊이가 K인 경우 N개의 결점이 있는 두 갈래 나무는 각 결점이 깊이가 K인 만 두 갈래 나무의 번호가 1부터 n까지의 결점과 일일이 대응할 때만 완전 두 갈래 나무라고 부른다.만약에 두 갈래 나무가 가장 아래의 두 층의 결점만 있는 도수가 2보다 작고 가장 아래층의 결점이 모두 이 층의 가장 왼쪽의 몇몇 위치에 집중된다면 이 두 갈래 나무는 완전한 두 갈래 나무가 된다.

적군이 포진하다.

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 52472    Accepted Submission(s): 21982
Problem Description
C국의 라이벌 A국은 그동안 군사훈련을 하고 있었기 때문에 C국의 스파이 두목 데릭과 그의 부하 티디는 또 바쁘게 움직이기 시작했다.A국은 해안선을 따라 직선으로 N개의 공병 캠프를 배치했는데 데릭과 티디의 임무는 이 공병 캠프의 활동 상황을 감시하는 것이다.어떤 선진적인 모니터링 수단을 채택했기 때문에 모든 공병 캠프의 인원수는 C국이 모두 파악하고 있다. 모든 공병 캠프의 인원수는 변동이 발생할 수 있고 약간의 인원을 증가하거나 줄일 수 있지만 이런 것들은 모두 C국의 감시를 피할 수 없다.
중앙정보국은 적들이 도대체 어떤 전술을 훈련하는지 연구해야 하기 때문에 티디는 수시로 데릭에게 어떤 연속된 공병 캠프가 모두 몇 명인지 보고해야 한다. 예를 들어 데릭은 "티디, 당장 세 번째 캠프부터 열 번째 캠프까지 모두 몇 명인지 보고해라!"라고 물었다.Tidy는 곧 이 단락의 총 인원수를 계산하여 보고할 것이다.그러나 적병 캠프의 인원수는 자주 변동한다. 데릭은 매번 묻는 단락이 다르기 때문에 티디는 매번 한 캠프씩 가서 세어야 한다. 곧 기진맥진한다. 데릭은 티디의 계산 속도에 대해 점점 불만스러워한다. "너 뚱뚱한 놈아, 이렇게 느리게 계산하면 해고해!"라고 티디는 생각했다. "너 혼자 계산해 봐. 이건 정말 힘든 일이야! 난 네가 나를 해고하는 게 미워!"어쩔 수 없이 Tidy는 컴퓨터 전문가인 Windbreaker에게 전화를 걸어 구조를 요청했다. Windbreaker는 말했다. "뚱뚱한 녀석, 평소에 acm 문제를 많이 풀고 알고리즘 책을 많이 보라고 했는데 이제 고과를 맛보겠지!"Tidy: "잘못 알았어..."하지만 윈드브레이크는 전화를 끊었습니다.Tidy는 매우 고민한다. 이렇게 하면 그는 정말 붕괴될 것이다. 똑똑한 독자, 너는 프로그램을 써서 그를 도와 이 일을 완성할 수 있니?그러나 만약 당신의 프로그램 효율이 높지 않다면, Tidy는 여전히 Derek의 꾸지람을 받을 것이다.
 
Input
첫 번째 줄에는 T 그룹 데이터가 있음을 나타내는 정수 T가 있습니다.
각 조의 데이터 첫 줄에 하나의 정수 N(N<=50000)은 적에게 N개의 공병 캠프가 있음을 나타낸다. 그 다음에 N개의 정수가 있고 i번째 정수 ai는 i번째 공병 캠프가 시작될 때ai개인(1<=ai<=50)을 대표한다.
다음 줄마다 하나의 명령이 있고 명령은 네 가지 형식이 있다.
(1) Add i j, i와 j는 정수로 제 캠프의 j 개인 증가를 나타낸다(j는 30을 초과하지 않는다)
(2) Sub ij, i와 j는 정수로 제 i캠프가 j개인을 줄인다는 것을 나타낸다(j는 30을 초과하지 않는다).
(3)Query ij, i와 j는 정수이고 i<=j는 제이에서 제이 캠프까지의 총 인원수를 묻는다.
(4) End는 종료를 나타내며 이 명령은 각 그룹의 데이터 마지막에 나타납니다.
그룹당 최대 40000개의 명령
 
Output
i그룹 데이터에 대해 먼저 "Case i:"및 리턴을 출력하고
모든 Query 질문에 대해 정수를 출력하고 리턴합니다. 질문한 단락의 총 인원수를 나타냅니다. 이 숫자는 int 안에 유지됩니다.
 
Sample Input

   
   
   
   

    
    
    
    1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Case 1:
6
33
59
   
   
   
   

코드:

#include<cstdio>
#include<cstring>
using namespace std;

struct node
{
    int l,r,x;
    node(){}
    node(int a,int b,int c):l(a),r(b),x(c){}
};

node a[400000];// 
int ans;

void build(int l,int r,int i)
{
    a[i]=node(l,r,0);
    if(l==r)
        return;
    int mid=(l+r)/2;
    build(l,mid,2*i);
    build(mid+1,r,2*i+1);
}

void update(int p,int add,int i)// 
{
    if(a[i].l==a[i].r&&a[i].r==p)
    {
        a[i].x+=add;
        return;
    }
    // 
    int mid=(a[i].l+a[i].r)/2;
    if(p<=mid)
        update(p,add,2*i);
    else
        update(p,add,2*i+1);
    // 
    /*update(p,add,2*i);
    update(p,add,2*i+1);*/
    a[i].x=a[2*i].x+a[2*i+1].x;// 
}

void query(int l,int r,int i)
{
    if(a[i].l==l&&a[i].r==r)
    {
        ans+=a[i].x;
        return;
    }
    int mid=(a[i].l+a[i].r)/2;
    if(r<=mid)
        query(l,r,2*i);
    else if(l>=mid+1)
        query(l,r,2*i+1);
    else
    {
        query(l,mid,2*i);
        query(mid+1,r,2*i+1);
    }
}

int main()
{
    int t;
    int n;
    int x;
    char str[10];
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        scanf("%d",&n);
        build(1,n,1);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            update(i,x,1);
        }
        printf("Case %d:
",k);
        while(scanf("%s",str)&&strcmp("End",str)!=0)
        {
            if(strcmp("Add",str)==0)
            {
                int i;
                scanf("%d%d",&i,&x);
                update(i,x,1);
            }
            if(strcmp("Sub",str)==0)
            {
                int i;
                scanf("%d%d",&i,&x);
                update(i,-x,1);
            }
            if(strcmp("Query",str)==0)
            {
                int l,r;
                ans=0;
                scanf("%d%d",&l,&r);
                query(l,r,1);
                printf("%d
",ans);
            }
        }
    }
    return 0;
}