敵兵布陣
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4546 Accepted Submission(s): 1818
Problem Description
C國的死對頭A國這段時間正在進行軍事演習，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線布置了N個工兵營地,Derek和Tidy的任務就是要監(jiān)視這些工兵營地的活動情況。由于采取了某種先進的監(jiān)測手段，所以每個工兵營地的人數(shù)C國都掌握的一清二楚,每個工兵營地的人數(shù)都有可能發(fā)生變動，可能增加或減少若干人手,但這些都逃不過C國的監(jiān)視。
中央情報局要研究敵人究竟演習什么戰(zhàn)術,所以Tidy要隨時向Derek匯報某一段連續(xù)的工兵營地一共有多少人,例如Derek問:“Tidy,馬上匯報第3個營地到第10個營地共有多少人!”Tidy就要馬上開始計算這一段的總人數(shù)并匯報。但敵兵營地的人數(shù)經(jīng)常變動，而Derek每次詢問的段都不一樣，所以Tidy不得不每次都一個一個營地的去數(shù)，很快就精疲力盡了，Derek對Tidy的計算速度越來越不滿:"你個死肥仔，算得這么慢，我炒你魷魚!”Tidy想：“你自己來算算看，這可真是一項累人的工作!我恨不得你炒我魷魚呢!”無奈之下，Tidy只好打電話向計算機專家Windbreaker求救,Windbreaker說：“死肥仔，叫你平時做多點acm題和看多點算法書，現(xiàn)在嘗到苦果了吧!”Tidy說："我知錯了。。。"但Windbreaker已經(jīng)掛掉電話了。Tidy很苦惱，這么算他真的會崩潰的，聰明的讀者，你能寫個程序幫他完成這項工作嗎？不過如果你的程序效率不夠高的話，Tidy還是會受到Derek的責罵的.
Input
第一行一個整數(shù)T，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)第一行一個正整數(shù)N（N<=50000）,表示敵人有N個工兵營地，接下來有N個正整數(shù),第i個正整數(shù)ai代表第i個工兵營地里開始時有ai個人（1<=ai<=50）。
接下來每行有一條命令，命令有4種形式：
(1) Add i j,i和j為正整數(shù),表示第i個營地增加j個人（j不超過30）
(2)Sub i j ,i和j為正整數(shù),表示第i個營地減少j個人（j不超過30）;
(3)Query i j ,i和j為正整數(shù),i<=j，表示詢問第i到第j個營地的總人數(shù);
(4)End 表示結束，這條命令在每組數(shù)據(jù)最后出現(xiàn);
每組數(shù)據(jù)最多有40000條命令
Output
對第i組數(shù)據(jù),首先輸出“Case i:”和回車,
對于每個Query詢問，輸出一個整數(shù)并回車,表示詢問的段中的總人數(shù),這個數(shù)最多不超過1000000。
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
題目分析 :
看了 一下午的書, 終于有一點明白了樹狀數(shù)組這東西 , 果然還是要做題啊, 一直不明白的地方, 刷了這
水題后, 貌似明白了一點了 
.
這是一道純粹的 樹狀數(shù)組 的題目, 有模板的話直接模板就可以AC了, 不過手打也用不了什么時間.
因為查詢語句是固定的, 所以不需要用 字符串比較函數(shù), 直接比較首字符就可以了, 剛開始的時候想偷
懶, 把 quy 函數(shù)寫成 quy ( int x, int y ) , 想一次就把結果求出來......還是對樹狀數(shù)組的理解不深刻......從其
結構而言, 這種想法就不可能實現(xiàn).
簡單介紹下 樹狀數(shù)組 :
樹狀數(shù)組是一個查詢和修改復雜度都為log(n)的數(shù)據(jù)結構，假設數(shù)組a[1...n]，那么查詢a[1] + …… + a[i] 的時間是log級別的，而且是一個在線的數(shù)據(jù)結構，支持隨時修改某個元素的值，復雜度也為log級別。
來觀察一下這個圖：
令這棵樹的結點編號為C1，C2……Cn。令每個結點的值為這棵樹的值的總和，那么容易發(fā)現(xiàn)：
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
……
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
這里有一個有趣的性質，下午推了一下發(fā)現(xiàn)：
設節(jié)點編號為x，那么這個節(jié)點管轄的區(qū)間為2^k（其中k為x二進制末尾0的個數(shù)）個元素。因為這個區(qū)間最后一個元素必然為Ax，所以很明顯：
Cn = A(n – 2^k + 1) + …… + An
算這個2^k有一個快捷的辦法，定義一個函數(shù)如下即可：
int lowbit(int x){
return x & (x ^ (x – 1));
}
當想要查詢一個SUM(n)時，可以依據(jù)如下算法即可：
step1: 令sum = 0，轉第二步；
step2: 假如n <= 0，算法結束，返回sum值，否則sum = sum + Cn，轉第三步；
step3: 令n = n – lowbit(n)，轉第二步。
可以看出，這個算法就是將這一個個區(qū)間的和全部加起來，為什么是效率是log(n)的呢？以下給出證明：
n = n – lowbit(n)這一步實際上等價于將n的二進制的最后一個1減去。而n的二進制里最多有log(n)個1，所以查詢效率是log(n)的。
那么修改呢，修改一個節(jié)點，必須修改其所有祖先，最壞情況下為修改第一個元素，最多有log(n)的祖先。所以修改算法如下（給某個結點i加上x）：
step1: 當i > n時，算法結束，否則轉第二步；
step2: Ci = Ci + x， i = i + lowbit(i)轉第一步。
i = i +lowbit(i)這個過程實際上也只是一個把末尾1補為0的過程。
//修改過程必須滿足減法規(guī)則！
所以整個程序如下：
const int MAX = 50000;
#define lowbit(x) ((x)&(-x))
int com[ MAX + 1 ],N,T;
void modify ( int pos, int val ){
while ( pos <= N ){
com[pos] += val;
pos = pos + lowbit(pos);
}
}
int quy ( int x ){
int sum = 0;
while ( x > 0 ){
sum = sum + com[x];
x = x - lowbit(x);
}
return sum;
}
初始化 : for ( int i = 1; i <= N; ++ i ){
scanf ( "%d",&x );
modify ( i, x );
}
----------------------------------------------------------------------------------------------------------------------------
本題代碼如下 :
/*
MiYu原創(chuàng), 轉帖請注明 : 轉載自 ______________白白の屋
http://www.cnblog.com/MiYu
Author By : MiYu
Test : 1
Program : 1166
*/
#include <iostream>
using namespace std;
const int MAX = 50000;
#define lowbit(x) ((x)&(-x))
int com[ MAX + 1 ],N,T;
void modify ( int pos, int val ){
while ( pos <= N ){
com[pos] += val;
pos = pos + lowbit(pos);
}
}
int quy ( int x ){
int sum = 0;
while ( x > 0 ){
sum = sum + com[x];
x = x - lowbit(x);
}
return sum;
}
int main ()
{
while ( scanf ( "%d",&T ) != EOF ){
int ca = 1,x,y;
while ( T -- ){
printf ( "Case %d:\n",ca++ );
scanf ( "%d",&N );
for ( int i = 0; i <= N; ++ i ) com[i] &= 0;
for ( int i = 1; i <= N; ++ i ){
scanf ( "%d",&x );
modify ( i, x );
}
char ask[10];
while ( scanf ( "%s",ask ), ask[0] != 'E' ){
scanf ( "%d%d",&x,&y );
switch ( ask[0] ){
case 'A': modify ( x, y ); break;
case 'S': modify ( x, -y ); break;
case 'Q': printf ( "%d\n",quy ( y ) - quy ( x-1 ) ); break;
}
}
}
}
return 0;
}