首页 > 笔记 > LCA问题详解

LCA问题详解

好久以前写的,也没用latex啥的,一直忘了放出来。(好像是noip前

离线算法 Tarjan

利用并查集优越的时空复杂度,我们可以实现LCA问题的O(n+Q)算法,这里Q表示询问的次数。

Tarjan算法基于深度优先搜索的框架,对于新搜索到的一个结点,首先创建由这个结点构成的集合,再对当前结点的每一个子树进行搜索,每搜索完一棵子树,则可确定子树内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树之外,这时把子树所形成的集合与当前结点的集合合并,并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树,直到当前结点的所有子树搜索完。这时把当前结点也设为已被检查过的,同时可以处理有关当前结点的LCA询问,如果有一个从当前结点到结点v的询问,且v已被检查过,则由于进行的是深度优先搜索,当前结点与v的最近公共祖先一定还没有被检查,而这个最近公共祖先的包涵v的子树一定已经搜索过了,那么这个最近公共祖先一定是v 所在集合的祖先。

这种算法在询问少的时候比较优越。但是我觉得不大实用就没写。

在线ST+dfs

RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。可以写一个线段树,但是预处理和查询的复杂度都是O(logn)。这里有更牛的算法,就是ST(Sparse Table)算法,它可以做到O(nlogn)的预处理,O(1)地回答每个询问。

来看一下ST算法是怎么实现的(以最大值为例):
首先是预处理,用一个DP解决。设a[i]是要求区间最值的数列,f[i,j]表示从第i个数起连续2j个数中的最大值。例如数列

3 2 4 5 6 8 1 2 9 7

f[1,0]表示第1个数起,长度为20=1个数中的最大值,其实只有3这个数。f[1,2]=5,f[1,3]=8,f[2,0]=2,f[2,1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样,Dp的状态、初值都已经有了,剩下的就是状态转移方程。我们把f[i,j]的求值区间平均分成两段(因为2j一定是偶数),从i到i+2j-1-1为一段,i+2j-1到i+2j-1为一段(长度都为2j-1)。用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。f[i,j]就是这两段的最大值中的最大值。于是我们得到了动规方程

f[i][j]=max(f[i][j-1],f[i+2j-1][j-1])

F[i,j]表称为稀疏表(Sparse Table)。有了稀疏表,我们就可以做到O(1)时间查询任意区间的最值。如在上例中我们要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间长度为22,最大值我们可以直接由f[2,2]和f[5,2]得到。扩展到一般情况,就是把区间[l,r]分成两个长度为2j的区间(保证有f[i,j]对应,其中2j为小于r-l+1的最大值)。即,q[l,r] 表示 从第l个数到第r个数中最大的数,那么:

q[l][r]=max(f[l][j],f[r-2j+1][j]);

 编程时,注意1<<i=2^i

例题 luogu1816

题解

好了,回归我们的LCA问题

LCA 问题可以转化为 RMQ 问题求解,方法为:

观察:节点u与v的LCA正是对树T进行深度优先遍历过程中u节点与v节点之间的具有最浅深度的节点,下图展示了对一颗树的深度优先遍历过程,以及形成的欧拉迹。

images

注:设树节点数为n,则欧拉迹的大小为2n-1
对于一颗树T,我们创建三个数组: E [1,..,2n-1],存放树T的欧拉迹,E[i]表示欧拉迹中第i个节点的标号;L [1,..2n-1],存放欧拉迹中各节点的深度,根节点深度为0; R [1,..n],R[i]存放第i个节点在欧拉迹中第一次出现的位置。例如:

images
为了计算LCAT(x,y):
欧拉迹中处于x和y之间的所在节点为ER[x],..,R[y]。在这个子迹中,最浅节点的标号为RMQL(R[x],R[y]),这里RMQ算法查找最小节点的标号。此时LCAT(x,y)= RMQL(R[x],R[y])

代码

 


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×