HDU 1166 敵兵布陣(線段樹)

敵兵布陣

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 42921 Accepted Submission(s): 18164


Problem Description C國的死對頭A國這段時間正在進行軍事演習，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線布置了N個工兵營地,Derek和Tidy的任務就是要監視這些工兵營地的活動情況。由於采取了某種先進的監測手段，所以每個工兵營地的人數C國都掌握的一清二楚,每個工兵營地的人數都有可能發生變動，可能增加或減少若干人手,但這些都逃不過C國的監視。
中央情報局要研究敵人究竟演習什麼戰術,所以Tidy要隨時向Derek匯報某一段連續的工兵營地一共有多少人,例如Derek問:“Tidy,馬上匯報第3個營地到第10個營地共有多少人!”Tidy就要馬上開始計算這一段的總人數並匯報。但敵兵營地的人數經常變動，而Derek每次詢問的段都不一樣，所以Tidy不得不每次都一個一個營地的去數，很快就精疲力盡了，Derek對Tidy的計算速度越來越不滿:"你個死肥仔，算得這麼慢，我炒你鱿魚!”Tidy想：“你自己來算算看，這可真是一項累人的工作!我恨不得你炒我鱿魚呢!”無奈之下，Tidy只好打電話向計算機專家Windbreaker求救,Windbreaker說：“死肥仔，叫你平時做多點acm題和看多點算法書，現在嘗到苦果了吧!”Tidy說："我知錯了。。。"但Windbreaker已經掛掉電話了。Tidy很苦惱，這麼算他真的會崩潰的，聰明的讀者，你能寫個程序幫他完成這項工作嗎？不過如果你的程序效率不夠高的話，Tidy還是會受到Derek的責罵的.

Input 第一行一個整數T，表示有T組數據。
每組數據第一行一個正整數N（N<=50000）,表示敵人有N個工兵營地，接下來有N個正整數,第i個正整數ai代表第i個工兵營地裡開始時有ai個人（1<=ai<=50）。
接下來每行有一條命令，命令有4種形式：
(1) Add i j,i和j為正整數,表示第i個營地增加j個人（j不超過30）
(2)Sub i j ,i和j為正整數,表示第i個營地減少j個人（j不超過30）;
(3)Query i j ,i和j為正整數,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

Author Windbreaker
Recommend Eddy | We have carefully selected several similar problems for you: 1394 1698 1754 1542 1540

套用模板，如果有什麼理解錯誤，請指出，新人學步。
時間和空間都有些大。
代碼：

#include 
#include 
#include 
#include 
using namespace std;
#define M 50005
int a[M];
struct Node{
int left;
int right;
int count;
}node[4*M];   //開4倍大是因為變成二叉樹後節點有很多。
void TreeMake(int l,int r,int i)  //建立二叉樹。
{
    node[i].left=l;  //l是區間前界。
    node[i].right=r; //r是區間後界。
    if(l==r)         //區間長度只有1，那就可以得到確切的值。
    {
     node[i].count=a[l];
     return;
    }
    int m=(l+r)/2;  //否則還要接著劃分區間。
    TreeMake(l,m,2*i);
    TreeMake(m+1,r,2*i+1);
    node[i].count=node[2*i].count+node[2*i+1].count; //得到這個區間的和。
}
void TreeUpdate(int i,int x,int op,int num) //更新。
{
    int l=node[i].left;
    int r=node[i].right;
    int mid=(l+r)/2;
    if(x==l && x==r) //找到那個要更新的節點，就更新它。
    {
      if(op==1)
      node[i].count+=num;
      else
      node[i].count-=num;
      return;
    }
    if(x>mid)      //判斷那個要更新的點是在左子樹還是在右子樹。
    TreeUpdate(2*i+1,x,op,num); //進入左子樹。
    else
    TreeUpdate(2*i,x,op,num);   //進入右子樹。
    if(op==1)
    node[i].count+=num;         //這裡就是對每包含該節點的大區間都更新和值。
    else
    node[i].count-=num;
}
int TreeQuery(int l,int r,int i) //尋找要輸出和值的區間。
{
    int m=(node[i].left+node[i].right)/2;
    if(node[i].left==l && node[i].right==r)
    return node[i].count;
  //  if(node[i].left==node[i].right) return 0;  
  //發現沒有這句也能過，不知道是什麼，如果知道這句話是干什麼的，請告知。
    if(r<=m)  //如果後界比中間值小，整個區間都在左子樹內。
        return TreeQuery(l,r,i*2);
    else if(l>m) //同理，如果前界比中間值大，整個區間都在右子樹內。
        return TreeQuery(l,r,2*i+1);
    else     //如果區間被中間值分開，就分別求出來，再相加。
        return TreeQuery(l,m,2*i)+TreeQuery(m+1,r,2*i+1);
}

int main()
{
    int m,i,j,n,tmp;
    char cmd[10];
    int x,y;
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        printf("Case %d:\n",i);
        scanf("%d",&n);
        for(j=1;j<=n;j++)
        {
            scanf("%d",&a[j]);
        }
        TreeMake(1,n,1);
        while(scanf("%s",cmd))
        {
             if (cmd[0] == 'E') break;
            scanf("%d %d", &x, &y);
            if (cmd[0] == 'Q')
            {
                tmp = TreeQuery(x, y, 1);
                printf("%d\n", tmp);
            }
            else if (cmd[0] == 'A')
            {
                TreeUpdate(1, x, 1, y);
            }
            else
            {
                TreeUpdate(1, x, 2, y);
            }
        }
    }
    return 0;
}