The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3264 Balanced Lineup(RMQ问题,线段树解决)

最近在看线段树,发现线段树其实是一个非常有用的数据结构,用它可以在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以下),欢迎留言告诉我;

posted on 2009-07-23 19:29 abilitytao 阅读(1860) 评论(5)  编辑 收藏 引用

评论

# re: POJ 3264 Balanced Lineup(RMQ问题,线段树解决) 2009-07-24 09:21 nomination

你这种方法会不会比较繁琐难懂,我觉得直观的用排序算法不就好了吗?  回复  更多评论   

# re: POJ 3264 Balanced Lineup(RMQ问题,线段树解决)[未登录] 2009-07-24 12:56 abilitytao

@nomination
同学 难道你觉得做题的目的仅仅是为了AC吗?  回复  更多评论   

# re: POJ 3264 Balanced Lineup(RMQ问题,线段树解决) 2009-07-25 15:54 移动12530彩铃

看不懂~你们在研究什么  回复  更多评论   

# re: POJ 3264 Balanced Lineup(RMQ问题,线段树解决) 2009-08-16 17:04 hellobuy

好文章。  回复  更多评论   

# re: POJ 3264 Balanced Lineup(RMQ问题,线段树解决) 2010-05-09 12:13 wty

lz有个问题问下,会不会有许多节点永远查询不到,
边查边建树会不会好一点  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理