首页 > 程序开发 > 综合编程 > 其他综合 > 正文
RMQ算法以及LCA的ST算法。
2017-05-17       个评论    来源:Fgaoshihao的博客  
收藏    我要投稿

RMQ算法以及LCA的ST算法。RMQ是一种求静态区间最值的算法,这种算法可以先用nlogn的时间做预处理,然后每次用O(1)的时间查询。RMQ有一点DP的思想,而且也是一种非常好理解的算法。相比线段树,线段树虽然可以求动态的区间最值,RMQ更好写,而且线段树O(logn)的时间操作一遍,当询问次数大的时候就有可能不如RMQ算法。

RMQ算法可以用f[i][j]表示在以i位开头的长度为2^j区间的最大值(或最小值,也可以是其他的区间最值)。

那么根据定义可以得出:f[i][0]=a[i] 这是非常显然的。

然后我们还可以得出DP方程:f[i][j]=max(f[i][j-1],f[i+(1<<(j-1)][j-1]);

这个DP方程是什么意思呢:我们把2^j这个区间分成两半,一半是从i开始长度为2^(j-1)的区间,另一半是起点为i+2^j,同样长度是2^(j-1)的区间。然后就可以的到以上的方程。

然后可以预处理的伪代码:

	for(int j=1;(1<
另外,RMQ算法在f数组中可以不存最大值,而去计这个区间取得最大值的编号,这样在一些情况下可能会比较方便,而且等一下要讲的LCA中的RMQ也是存储编号的。

讲回RMQ算法,既然已经讲了预处理,那么怎么用O(1)的时间去求呢?可能会有人说两个区间不完全会是2^j。但是RMQ查询的是区间最值,所以可以把两个区间互相包含的放在一起,其实这也就是为什么RMQ只能计算区间最值。有了两个区间互相包含的思想,查询就非常简单了:

	int k=log(y-x+1.0) / log(2.0);
	printf("%d\n",max(maxx[x][k],maxx[y-(1<其中k就是计算要查询的区间长度是2的多少次方。因为这个区间的长度不可能为小数嘛,这里的k就会自动向下取整,因为向下取整的话,把这个区间分成两半后的长度是一定会足以覆盖这个区间的,所以直接把区间分成两半,像预处理那样就行了。

LCA:最近公共祖先算法。LCA就是计算在一棵树上,x节点和y节点他们最近的公共祖先是哪一个节点(最近的意义通俗一点来说就是离根最远)。首先LCA有三种算法Tarjan,ST算法和倍增法,其中Tarjan是离线算法,ST算法和倍增法都是在线算法。本文讲的就是ST算法。ST算法可以用O(nlogn)的时间复杂度来预处理,然后每次用O(1)算出每两个点之间的最近公共祖先。

首先LCA要做的是在树上做一次DFS,记住每一个节点第一次出现的时间戳first[i],并且用node[tot]表示在时间戳为tot时遍历到的节点,还要用一个dep[tot]表示在时间戳为tot时遍历到的节点的深度。假如现在有这样一棵树:\

先讲讲遍历的顺序:1242565752131

然后搜索出来的node和dep数组会是这样的。

时间戳:1 2 3 4 5 6 7 8 9 10 11 12 13

node :1 2 4 2 5 6 5 7 5 2 1 3 1

dep :1 2 3 2 3 4 3 4 3 2 1 2 1

然后first数组为:

节点编号:1 2 3 4 5 6 7

first :1 2 12 3 5 6 8

然后ST的算法过程就是:

比如说查询的是4与7的LCA,first[4]=3,first[7]=8,那我们找在时间戳为3-8的dep数组中dep[4]是最小的,然后node[4]对应的节点是2,那么4和7的LCA就是2.

说了这么多,相信大家都对ST算法的LCA有了一定的了解了吧。

再讲讲这个算法的原理。在first[i]-first[j]当中遍历到的节点,一定会是他们的LCA节点的子树中的节点,那么其中dep最小的不就是这个根吗(也就是他们的LCA)。

其中dep求最小值,可以用到RMQ来算。这样就是LCA_ST算法了,代码如下:

#include
#include
#include
#include
#include
#include
#include
#define Maxn 20020
using namespace std;
int node[Maxn];
int dis[Maxn];
int dep[Maxn];
int first[Maxn];
int rmq[Maxn][16];
int father[Maxn];
vector son[Maxn];
int tot,n;
void dfs(int u)
{
	node[++tot]=u;
	dis[u]=dis[father[u]]+1;
	dep[tot]=dis[u];
	if(first[u]==0) first[u]=tot;
	for(int i=0;i
   
点击复制链接 与好友分享!回本站首页
上一篇:Unity Shader-时空扭曲效果
下一篇:ETL工具-kettle安装部署
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站