HDU 1166 線段樹單點更新+區(qū)間查詢?nèi)腴T

題面：

敵兵布陣 Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 61888????Accepted Submission(s): 26149


Problem Description C國的死對頭A國這段時間正在進行軍事演習，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線布置了N個工兵營地,Derek和Tidy的任務就是要監(jiān)視這些工兵營地的活動情況。由于采取了某種先進的監(jiān)測手段，所以每個工兵營地的人數(shù)C國都掌握的一清二楚,每個工兵營地的人數(shù)都有可能發(fā)生變動，可能增加或減少若干人手,但這些都逃不過C國的監(jiān)視。
中央情報局要研究敵人究竟演習什么戰(zhàn)術(shù),所以Tidy要隨時向Derek匯報某一段連續(xù)的工兵營地一共有多少人,例如Derek問:“Tidy,馬上匯報第3個營地到第10個營地共有多少人!”Tidy就要馬上開始計算這一段的總?cè)藬?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個營地的總?cè)藬?shù);
(4)End 表示結(jié)束，這條命令在每組數(shù)據(jù)最后出現(xiàn);
每組數(shù)據(jù)最多有40000條命令
?
Output 對第i組數(shù)據(jù),首先輸出“Case i:”和回車,
對于每個Query詢問，輸出一個整數(shù)并回車,表示詢問的段中的總?cè)藬?shù),這個數(shù)保持在int以內(nèi)。
?
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

題目大意：

? ? 一共有n個兵營，每個兵營初始有ai個人。對應3種操作。

操作一：

? ? Q A B 詢問A到B共多少人。

操作二：

? ? A X Y 給X兵營加Y個人。

操作三：

? ? S X Y 給X兵營減去Y個人。

解題：

? ? 直接做，復雜度過高。用線段樹維護，區(qū)間和。每種操作復雜度都為log（n）。

代碼：

#include#include#define?maxn?50010
#define?ls?i<<1
#define?rs?(i<<1)|1
using?namespace?std;
struct?node
{
	//左右邊界，區(qū)間和?
????int?l,r,sum;
}stree[maxn<>1;
????build(ls,l,mid);
????build(rs,mid+1,r);
????//維護區(qū)間和?
????push_up(i);
}
//單點更新?
void?update(int?i,int?x,int?v)
{
????if(x==stree[i].l&&x==stree[i].r)
????{
????????stree[i].sum+=v;
????????return;
????}
????//根據(jù)相對位置，向下遞歸?
????int?mid=(stree[i].l+stree[i].r)>>1;
????if(x>1;
????if(rmid)
????????return?query(rs,l,r);
????else
????????return?query(ls,l,mid)+query(rs,mid+1,r);
}?
int?main()
{
????int?t,n,tmp,x,v;
????char?oper[10];
????scanf("%d",&t);
????for(int?i=1;i<=t;i++)
????{
??????printf("Case?%d:n",i);
??????scanf("%d",&n);
??????//建樹?
??????build(1,1,n);
??????//初值?
??????for(int?j=1;j<=n;j++)
??????{
??????????scanf("%d",&tmp);
??????????update(1,j,tmp);
??????}
??????while(1)
??????{
??????????scanf("%s",oper);
??????????if(oper[0]=='E')
??????????????break;
??????????else?if(oper[0]=='A')
??????????{
?????????????scanf("%d%d",&x,&v);
?????????????update(1,x,v);
??????????}
??????????else?if(oper[0]=='S')
??????????{
??????????????scanf("%d%d",&x,&v);
??????????????update(1,x,-v);
??????????}
??????????else
??????????{
??????????????scanf("%d%d",&x,&v);
??????????????printf("%dn",query(1,x,v));
??????????}
??????}
????}
????return?0;
}