【转】POJ 3264 线段树解法

每个算法都是数学家或者计算机学家多年研究的结果，不是我自己臆造的，所以学习一个新算法的最佳方法还是看写的好的代码。

按照惯例，我就粘贴一个网上写的很好的帖子。。。

原文地址：http://ip96cns.blog.163.com/blog/static/17009519220112525029459/

线段树的查找：（感谢高手指点，虽然只是一点却让我把线段树的内容理顺了）这里是我的一些总结吧

          一个线段树的结点表示一个区间，同时结点中保存所需要的信息。

         如果询问区间正好为这个线段树的区间（左边界和右边界都相同），则返回该结点中保存的信息。

         否则，递归往下查询该结点的子结点（之后再返回的值就是子结点的值了，与当前结点无关了）

         一直到“元线段”-不可再分之线段。

         线段树的结点的区间包含所有子结点的区间，并且子结点只有两个，同时子结点区间为父结点的一半，（二叉树）

         往下查询的时候判断询问区间是否与当前结点表示区间的左右区间覆盖，有三种情况

        1，查询区间在该结点表示区间中点右边，此时只需要往右孩子查询

        2.查询区间在该结点表示区间中点左边，此时只需要往左孩子查询

        3.查询区间包含该结点中点，这个时候要把查询区间一分为2，即查询区间的左边界到中点，往左孩子查询，以及中点到查询区间的右边界，往右孩子查询。 

这里线段树我用了两种实现方式，不过在渐进复杂度上差别不大。当然这题目RMQ才够快的。

我传了两个引用进去分别用来返回最大最小值。。。

第一种方法：

          .从1~n区间建立静态树，然后先给区间[i,i](就是左右边界相等的区间)赋值，然后再写个函数求其他区间。

第二种方法：

          从1~n区间建立静态树，并且将其中最大最小值构造为极小和极大，接着对于每个输入数据，不断的包含该数据所属区间的最大最小值.比如说某个数据i在区间[l,r]中，修改这个区间的结点，然后再递归下去修改这个结点的子结点的区间.

（这样就不需要为输入数据的开辟一个数组，但是效果似乎似乎不太好。）

#include <iostream>
#include <stdio.h>
using namespace std;

struct node
{
 int l,r;
 int minvalue,maxvalue;
};
node nodes[10000000];
//
int cowheight[50010];
//
void queryinterval(int l,int r,int nodeindex,int& maxval,int& minval)
{
 if(nodes[nodeindex].l==l&&nodes[nodeindex].r==r)
 {
  maxval=nodes[nodeindex].maxvalue;
  minval=nodes[nodeindex].minvalue;
  return ;
 }
 if(l==r)
 {
  maxval=minval=cowheight[l];
  return ;
 }
 //
 int mid=(nodes[nodeindex].l+nodes[nodeindex].r)/2;
 // 这个地方调试了很久才发现。。。如果这里不错就节省半天了
 // mid=(l+r)/2 是错的，必须是mid=(nodes[nodeindex].l+nodes[nodeindex].r)/2
 if(l>mid) queryinterval(l,r,nodeindex*2+2,maxval,minval);
 else if(r<=mid) queryinterval(l,r,nodeindex*2+1,maxval,minval);
 else
 {
  int max1,min1,max2,min2;
  queryinterval(l,mid,nodeindex*2+1,max1,min1);
  queryinterval(mid+1,r,nodeindex*2+2,max2,min2);
  maxval=max1>max2?max1:max2;
  minval=min1<min2?min1:min2;
  return ;
 }
}
//
//
void creattree(int l,int r,int index)
{
 nodes[index].l=l;
 nodes[index].r=r;
 if(l==r)
 {
  nodes[index].maxvalue=nodes[index].minvalue=cowheight[l];
  return;
 }
 creattree(l,(l+r)/2,index*2+1);
 creattree((l+r)/2+1,r,index*2+2);
}
void addvalue(int index,int& maxval,int& minval)
{
 if(nodes[index].l==nodes[index].r)
 {
  minval=maxval=nodes[index].maxvalue;
  return ;
 }
 int max1,min1,max2,min2;
 addvalue(index*2+1,max1,min1);
 addvalue(index*2+2,max2,min2);
 nodes[index].maxvalue=max1>max2?max1:max2;
 nodes[index].minvalue=min1<min2?min1:min2;
 maxval=nodes[index].maxvalue;
 minval=nodes[index].minvalue;
 return ;
}
//
int main()
{
 int n,q;
 scanf("%d%d",&n,&q);
 //
 int i;
 for(i=1;i<=n;i++)
  scanf("%d",&cowheight[i]);
 //建树
 creattree(1,n,0);
 int l,u;
 addvalue(0,l,u);
 //
 for(i=0;i<q;i++)
 {
  int a,b;
  scanf("%d%d",&a,&b);
  int maxval,minval;
  queryinterval(a,b,0,maxval,minval);
  printf("%d\n",maxval-minval);
 }
 return 0;
}

#include <iostream>
#include <stdio.h>
using namespace std;
struct node
{
int l,r;
int minvalue,maxvalue;
node(){maxvalue=0; minvalue=0x7fffffff; }
}; node nodes[131072];
//
//
void queryinterval(int l,int r,int nodeindex,int& maxval,int& minval)
{
if(nodes[nodeindex].l==l&&nodes[nodeindex].r==r)
{
maxval=nodes[nodeindex].maxvalue;
minval=nodes[nodeindex].minvalue;
return ;
}
//
int mid=(nodes[nodeindex].l+nodes[nodeindex].r)/2;
if(l>mid) queryinterval(l,r,nodeindex*2+2,maxval,minval);
else if(r<=mid) queryinterval(l,r,nodeindex*2+1,maxval,minval);
else
{
int max1,min1,max2,min2;
queryinterval(l,mid,nodeindex*2+1,max1,min1);
queryinterval(mid+1,r,nodeindex*2+2,max2,min2);
maxval=max1>max2?max1:max2;
minval=min1<min2?min1:min2;
return ;
}
}
//
//
void creattree(int l,int r,int index)
{
nodes[index].l=l;
nodes[index].r=r;
if(l<r)
{
creattree(l,(l+r)/2,index*2+1);
creattree((l+r)/2+1,r,index*2+2);
}
}
void addvalue(int pos,int val,int nodeindex)
{
if(nodes[nodeindex].l==nodes[nodeindex].r)
{
nodes[nodeindex].maxvalue=nodes[nodeindex].minvalue=val;
return ;
}
//
if(nodes[nodeindex].maxvalue<val) nodes[nodeindex].maxvalue=val;
if(nodes[nodeindex].minvalue>val) nodes[nodeindex].minvalue=val;
//
int mid=(nodes[nodeindex].l+nodes[nodeindex].r)/2;
if(pos<=mid) addvalue(pos,val,nodeindex*2+1);
else         addvalue(pos,val,nodeindex*2+2);
}
//
int main()
{
int n,q;
scanf("%d%d",&n,&q);
//
creattree(1,n,0);
int i,cowheight;
for(i=1;i<=n;i++)
{
scanf("%d",&cowheight);
addvalue(i,cowheight,0);
}
//
for(i=0;i<q;i++)
{
int a,b;
scanf("%d%d",&a,&b);
int maxval,minval;
queryinterval(a,b,0,maxval,minval);
printf("%d\n",maxval-minval);
}
return 0;
}