最近在看線段樹，發(fā)現(xiàn)線段樹其實(shí)是一個(gè)非常有用的數(shù)據(jù)結(jié)構(gòu)，用它可以在logL的時(shí)間內(nèi)完成一條線段的插入，查詢等，由于線段樹的特殊性質(zhì)，使得它在處理某些區(qū)間的問題上具有不可替代的優(yōu)越性。
POJ3264的題意是這樣的，給你一串?dāng)?shù)字，再給你一個(gè)區(qū)間[a,b]，求區(qū)間[a,b]上最大數(shù)減去最小數(shù)的最大值，即經(jīng)典的RMQ問題。
方法是首先建立[1，n]的線段樹，然后向線段樹中插入所有線段，其實(shí)在這里指的就是葉子，因?yàn)槿~子可以認(rèn)為是[a,a]的線段，插入的途中，修改每一個(gè)節(jié)點(diǎn)所對(duì)應(yīng)區(qū)間的最大值和最小值（這里是先序遍歷），然后再查詢即可。查詢的時(shí)候，只有當(dāng)當(dāng)前線段完全覆蓋時(shí)，才更新信息返回，否則應(yīng)該繼續(xù)往下查詢，直到覆蓋為止！
個(gè)人通過這個(gè)題對(duì)線段樹的領(lǐng)悟得到的極大的加深，線段樹將一個(gè)很大區(qū)間的插入查詢問題分解成為很多小區(qū)間的行為，再把它們進(jìn)行組合，從而得到結(jié)果。這是因?yàn)槟阍趯?duì)比你查詢區(qū)間大的區(qū)間上查詢，結(jié)果是不精確的（想想為什么？），所以，只有分解到小區(qū)間上，才能夠獲得準(zhǔn)確的答案~
代碼如下：
//This is the source code for POJ 3264
//created by abilitytao
//2009年7月23日19:11:55
//attention:This is the my first time to use the Segment Tree,congratulations!
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define MAX 10000000
//由于N即為線段樹最底層的節(jié)點(diǎn)數(shù)，則線段樹最高為(ceil)log2 N+1=17層；
//則線段樹最多有2^17-1個(gè)節(jié)點(diǎn)=131071
//上述節(jié)點(diǎn)數(shù)絕對(duì)滿足要求
struct node
{
int left;
int right;
int min;
int max;
node *lchild;
node *rchild;
}nodeset[MAX];//我們預(yù)先構(gòu)造出這些節(jié)點(diǎn)可以節(jié)省大量動(dòng)態(tài)建立節(jié)點(diǎn)的時(shí)間
int minnum;
int maxnum;
node *Newnode()//封裝一個(gè)新建節(jié)點(diǎn)的函數(shù)，可以把一些“構(gòu)造函數(shù)”寫在里面
{
static int count=0;//靜態(tài)變量
node *temp=&nodeset[count++];
temp->max=-99999999;//初始化max
temp->min=99999999;//初始化min
temp->lchild=NULL;
temp->right=NULL;
return temp;
}
node *Build(int l,int r)//建立區(qū)間l到區(qū)間r上的線段樹
{
node *root=Newnode();
root->left=l;
root->right=r;
if(l+1<=r)
{
int mid=(l+r)>>1;
root->lchild=Build(l,mid);
root->rchild=Build(mid+1,r);
}
return root;
}
void Insert(node *root,int i,int num)//插入節(jié)點(diǎn)，實(shí)際上是同步更新線段上的最大最小值
{
if(root->left==i&&root->right==i)
{
root->max=num;
root->min=num;
return ;
}
if(root->min>num)
root->min=num;
if(root->max<num)
root->max=num;
if(root->lchild->left<=i&&root->lchild->right>=i)
Insert(root->lchild,i,num);
else if(root->rchild->left<=i&&root->rchild->right>=i)
Insert(root->rchild,i,num);
}
void Query(node *root,int l,int r)//查詢函數(shù)
{
if(root->min>minnum&&root->max<maxnum)
return;//這兩句實(shí)際上是剪枝，入過當(dāng)前線段上的最小值比我已經(jīng)查詢到的最小值還大，可以不必再往下查詢（反之亦然） ^_^
if(root->left==l&&root->right==r)
{
if(root->min<minnum)
minnum=root->min;
if(root->max>maxnum)
maxnum=root->max;
return ;
}//只有當(dāng)線段被完全覆蓋時(shí)，才查詢線段中的信息
if(root->lchild->left<=l&&root->lchild->right>=r)
Query(root->lchild,l,r);//若可以查詢左兒子，查詢之
else if(root->rchild->left<=l&&root->rchild->right>=r)
Query(root->rchild,l,r);//若可以查詢有兒子，查詢之
else
{
int mid=(root->left+root->right)>>1;
Query(root->lchild,l,mid);
Query(root->rchild,mid+1,r);
}//若被查詢線段被中間階段，則分別查詢之
}
int main()
{
int n,q;
node *root;
scanf("%d%d",&n,&q);
root=Build(1,n);//建立線段樹
int i;
for(i=1;i<=n;i++)
{
int num;
scanf("%d",&num);
Insert(root,i,num);
}//完成全部插入
for(i=1;i<=q;i++)
{
maxnum=-99999999;
minnum=99999999;
int a,b;
scanf("%d%d",&a,&b);
Query(root,a,b);
printf("%d\n",maxnum-minnum);
}//查詢，輸出
return 0;
}
如果有什么疑問或者改進(jìn)方法（我想進(jìn)辦法也不能把它優(yōu)化到1000MS以下），歡迎留言告訴我；