線段樹
線段樹是一種二叉搜索樹，與區(qū)間樹相似，它將一個區(qū)間劃分成一些單元區(qū)間，每個單元區(qū)間對應線段樹中的一個葉結(jié)點。
接下來的幾篇文章我可能會多總結(jié)一些關(guān)于線段樹的題目、擴展及其用法，幫助一些不太懂線段樹的ACMer和未來忘記線段樹的自己……
例題
題意
中文題題意就不解釋了。下面我們用糖果來進行相關(guān)說明，桌上有n堆糖果，給你每堆糖果的初始數(shù)量，然后進行一些操作，這些操作可以往指定的糖果堆里放糖果，也可以往指定的糖果堆里拿走糖果，也可以詢問第a~b堆糖果的總數(shù)是多少。對于每次詢問，輸出這幾堆糖果的總數(shù)
導學
可能讀者以前沒接觸過線段樹，我借這道題形容一下。如果你用數(shù)組來維護這一堆糖果，那么增加和減少可能比較方便，但是計算總和的時候每一次詢問操作都需要重新循環(huán)，肯定就超時了
那么使用線段樹的好處在哪里呢？比如10堆糖果，它把這線型的10堆糖果變成了樹型。整一棵樹的所有葉節(jié)點存儲的是每一堆糖果的數(shù)量，而其葉節(jié)點的父節(jié)點則存儲了該節(jié)點下所有子節(jié)點的糖果數(shù)的總和。依次往上，根節(jié)點存儲的也就是所有糖果堆的總和
增加/減少糖果時，找到該糖果所在的葉節(jié)點的位置，更新，并且更新所有與該葉節(jié)點有關(guān)的“父節(jié)點”，在查詢時，就不需要重新計算了，將指定父節(jié)點的位置相加即可。
解析
在這題中，首先建立一個空的線段樹，即假設每堆糖果的數(shù)量為0
void build(int l,int r,int p){ //構(gòu)造線段樹
tree[p].left=l; //節(jié)點所表示的范圍起點
tree[p].right=r; //節(jié)點所表示的范圍終點
tree[p].value=0; //糖果的數(shù)量初始置0
if(l==r) return;
int mid=(l+r)/2;
build(l,mid,p*2); //依次建立子節(jié)點，直到處理到葉節(jié)點為止
build(mid+1,r,p*2+1);
}
……
cin>>n; //糖果的堆數(shù)
build(1,n,1);
然后得到每一堆糖果的具體數(shù)量。對于每一堆的數(shù)量，其實就相當于在原來置0的情況下，進行依次增加操作，往第i堆中增加value個糖果。
void add(int k,int p,int value){
if(tree[p].left==k&&tree[p].right==k){ //如果找到了對應位置的葉子節(jié)點，就進行增加操作
tree[p].value+=value;
return;
}
int mid=(tree[p].left+tree[p].right)/2; //從子節(jié)點中尋找
if(k<=mid) add(k,p*2,value);
else add(k,p*2+1,value);
tree[p].value = tree[2*p].value+tree[2*p+1].value; //子節(jié)點更新了，父節(jié)點也要更新
}
……
for(i=1;i<=n;i++){
scanf("%d",&num);
add(i,1,num);
}
然后，在上述操作的基礎上，我們發(fā)現(xiàn)已經(jīng)解決了題目要求的增加和減少的命令了，因為減少n等于增加-n。還有最后一個查詢的操作，也就是查詢a~b堆的總數(shù)
void search(int l,int r,int p){
if(tree[p].left==l&&tree[p].right==r){ //如果這個節(jié)點的范圍完全吻合所需要查找的范圍
sum+=tree[p].value; //直接增加
return; //加完就跑
}
//如果這個節(jié)點的范圍不滿足怎么辦？
int mid = (tree[p].left+tree[p].right)/2; //取當前范圍的中點
if(r<=mid) search(l,r,2*p); //如果所求范圍在中點左邊，往左子樹找
else if(l>mid) search(l,r,2*p+1); //如果所求范圍在中點右邊，往右子樹找
else{
//如果mid在所有范圍當中，也就是左子樹也有，右子樹也有，那就都找，但是需要處理一下范圍，不能直接傳遞l和r
search(l,mid,2*p);
search(mid+1,r,2*p+1);
}
}
……
sum=0;
search(num1,num2,1);
cout<<sum<<endl;
上面的查詢操作也是這個代碼的核心操作，和數(shù)組查詢不同的是，數(shù)組查詢每次都是在查詢?nèi)~節(jié)點，而線段樹幾乎不會到葉節(jié)點，總是到某個父節(jié)點就停下了，所以大大減少了操作次數(shù)
AC代碼
#include <iostream>
#include <string.h>
#include <stdio.h>
#define M 50005
using namespace std;
int sum;
struct node{
int left;
int right;
int value;
}tree[4*M]; //大小為預定長度的4倍
void build(int l,int r,int p){ //構(gòu)造線段樹
tree[p].left=l; //節(jié)點所表示的范圍起點
tree[p].right=r; //節(jié)點所表示的范圍終點
tree[p].value=0; //糖果的數(shù)量初始置0
if(l==r) return;
int mid=(l+r)/2;
build(l,mid,p*2); //依次建立子節(jié)點，直到處理到葉節(jié)點位置
build(mid+1,r,p*2+1);
}
void add(int k,int p,int value){
if(tree[p].left==k&&tree[p].right==k){ //如果找到了對應位置的葉子節(jié)點，就進行增加操作
tree[p].value+=value;
return;
}
int mid=(tree[p].left+tree[p].right)/2; //從子節(jié)點中尋找
if(k<=mid) add(k,p*2,value);
else add(k,p*2+1,value);
tree[p].value = tree[2*p].value+tree[2*p+1].value; //子節(jié)點更新了，父節(jié)點也要更新
}
void search(int l,int r,int p){
if(tree[p].left==l&&tree[p].right==r){ //如果這個節(jié)點的范圍完全吻合所需要查找的范圍
sum+=tree[p].value; //直接增加
return; //加完就跑
}
//如果這個節(jié)點的范圍不滿足怎么辦？
int mid = (tree[p].left+tree[p].right)/2; //取當前范圍的中點
if(r<=mid) search(l,r,2*p); //如果所求范圍在中點左邊，往左子樹找
else if(l>mid) search(l,r,2*p+1); //如果所求范圍在終點右邊，往右子樹找
else{ //如果mid在所有范圍當中，也就是左子樹也有，右子樹也有，那就都找，但是需要處理一下范圍，不能直接傳遞l和r
search(l,mid,2*p);
search(mid+1,r,2*p+1);
}
}
int main(){
char str[10];
int T,n,i,k,num,num1,num2;
cin>>T;
for(k=1;k<=T;k++){
cin>>n; //堆數(shù)
build(1,n,1);
for(i=1;i<=n;i++){
scanf("%d",&num);
add(i,1,num);
}
cout<<"Case "<<k<<":"<<endl;
while(scanf("%s",str)&&strcmp(str,"End")!=0){
scanf("%d%d",&num1,&num2);
if(strcmp(str,"Add")==0)
add(num1,1,num2);
else if(strcmp(str,"Sub")==0)
add(num1,1,-num2);
else{
sum=0;
search(num1,num2,1);
cout<<sum<<endl;
}
}
}
return 0;
}
