鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

LCA问题(最近公共祖先问题)+ RMQ问题

来源:互联网 作者:佚名 时间:2015-09-25 05:39
一、最近公共祖先(Least Common Ancestors) 对于有根树T的两个结点u、v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图,而LCA(T,u,v)即u到v的最短路上深度最小的点。 这里给出一个LC
一、最近公共祖先(Least Common Ancestors)


对于有根树T的两个结点u、v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图,而LCA(T,u,v)即u到v的最短路上深度最小的点。
这里给出一个LCA的例子:
例一
对于T=
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}
则有:
LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3


二、RMQ问题(Range Minimum Query)


RMQ问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在[i,j]里的最小值下标。这时一个RMQ问题的例子:
例二
对数列:5,8,1,3,6,4,9,5,7 有:
RMQ(2,4)=3
RMQ(6,9)=6
RMQ问题与LCA问题的关系紧密,可以相互转换,相应的求解算法也有异曲同工之妙。
下面给出LCA问题向RMQ问题的转化方法。
对树进行深度优先遍历,每当“进入”或回溯到某个结点时,将这个结点的深度存入数组E最后一位。同时记录结点i在数组中第一次出现的位置(事实上就是进入结点i时记录的位置),记做R[i]。如果结点E[i]的深度记做D[i],易见,这时求LCA(T,u,v),就等价于求 E[RMQ(D,R[u],R[v])],(R[u]
数列E[i]为:1,2,1,3,4,3,5,3,1
R[i]为:1,2,4,5,7
D[i]为:0,1,0,1,2,1,2,1,0
于是有:
LCA(T,5,2) = E[RMQ(D,R[2],R[5])] = E[RMQ(D,2,7)] = E[3] = 1
LCA(T,3,4) = E[RMQ(D,R[3],R[4])] = E[RMQ(D,4,5)] = E[4] = 3
LCA(T,4,5) = E[RMQ(D,R[4],R[5])] = E[RMQ(D,5,7)] = E[6] = 3
易知,转化后得到的数列长度为树的结点数的两倍加一,所以转化后的RMQ问题与LCA问题的规模同次


三、ST算法实现(以最大值为例):


首先是预处理,用一个DP解决。设a[i]是要求区间最值的数列,f[i, j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1,0]表示第1个数起,长度为2^0=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]平均分成两段(因为f[i,j]一定是偶数个数字),从i到i+2^(j-1)-1为一段,i+2^(j-1)到i+2^j-1为一段(长度都为2^(j-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 + 2^(j-1),j-1]).


接下来是得出最值,也许你想不到计算出f[i,j]有什么用处,一般毛想想计算max还是要O(logn),甚至O(n)。但有一个很好的办法,做到了 O(1)。还是分开来。如在上例中我们要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间的最大值我们可以直接由 f[2,2]和f[5,2]得到。扩展到一般情况,就是把区间[L,R]分成两个长度为2^n的区间(保证有f[i,j]对应)。直接给出表达式:
k :=[ ln(R-L+1) / ln(2)];
ans := max(F[L,k], F[R - 2^k+1, k]);
这样就计算了从i开始,长度为2^t次的区间和从r-2^i+1开始长度为2^t的区间的最大值(表达式比较烦琐,细节问题如加1减1需要仔细考虑.
四、试题


http://acm.pku.edu.cn/JudgeOnline/problem?id=2104


http://acm.pku.edu.cn/JudgeOnline/problem?id=2763


http://acm.pku.edu.cn/JudgeOnline/problem?id=3264


ZOJ 1141
上一篇:RMQ问题ST算法
下一篇:求组合数的问题
网友评论
<