最近在看线段树，发现线段树其实是一个非常有用的数据结构，用它可以在logL的时间内完成一条线段的插入，查询等，由于线段树的特殊性质，使得它在处理某些区间的问题上具有不可替代的优越性。
POJ3264的题意是这样的，给你一串数字，再给你一个区间[a,b]，求区间[a,b]上最大数减去最小数的最大值，即经典的RMQ问题。
方法是首先建立[1，n]的线段树，然后向线段树中插入所有线段，其实在这里指的就是叶子，因为叶子可以认为是[a,a]的线段，插入的途中，修改每一个节点所对应区间的最大值和最小值（这里是先序遍历），然后再查询即可。查询的时候，只有当当前线段完全覆盖时，才更新信息返回，否则应该继续往下查询，直到覆盖为止！
个人通过这个题对线段树的领悟得到的极大的加深，线段树将一个很大区间的插入查询问题分解成为很多小区间的行为，再把它们进行组合，从而得到结果。这是因为你在对比你查询区间大的区间上查询，结果是不精确的（想想为什么？），所以，只有分解到小区间上，才能够获得准确的答案~
代码如下：
//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即为线段树最底层的节点数，则线段树最高为(ceil)log2 N+1=17层；
//则线段树最多有2^17-1个节点=131071
//上述节点数绝对满足要求
struct node
{
int left;
int right;
int min;
int max;
node *lchild;
node *rchild;
}nodeset[MAX];//我们预先构造出这些节点可以节省大量动态建立节点的时间
int minnum;
int maxnum;
node *Newnode()//封装一个新建节点的函数，可以把一些“构造函数”写在里面
{
static int count=0;//静态变量
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)//建立区间l到区间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)//插入节点，实际上是同步更新线段上的最大最小值
{
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)//查询函数
{
if(root->min>minnum&&root->max<maxnum)
return;//这两句实际上是剪枝，入过当前线段上的最小值比我已经查询到的最小值还大，可以不必再往下查询（反之亦然） ^_^
if(root->left==l&&root->right==r)
{
if(root->min<minnum)
minnum=root->min;
if(root->max>maxnum)
maxnum=root->max;
return ;
}//只有当线段被完全覆盖时，才查询线段中的信息
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;
}
如果有什么疑问或者改进方法（我想进办法也不能把它优化到1000MS以下），欢迎留言告诉我；