LCA问题.pptVIP

最近公共祖先问题 Least Common Ancestors （LCA） 单个LCA问题的朴素算法 转化为RMQ（Range Minimal Query）问题来求解最近公共祖先 一般RMQ问题的Sparse Table（ST）算法 总结 LCA问题 给出一颗有根树T，对于任意两个结点u、v，求出LCA(T,u,v) ，即离根最远的结点x，使得x同时是u和v的祖先 朴素算法 单个LCA问题的朴素算法 从u的父亲开始顺着树往上枚举u的祖先并保存在一个列表L中，然后用类似的方法枚举v，当第一次发现某个祖先x在L中，则输出x 每次询问LCA(T,u,v)的复杂度为O(n) 引入RMQ问题 RMQ(Range Minimal Query) 给一个长度为n的数组A，回答询问RMQ(A,i,j)，即A[i..j]最小数的下标 LCA问题转化为RMQ问题 给树T做深度优先遍历,并记录下每次到达的结点 第一个记录的结点是根root(T),每经过一条边都记录它的端点,由于每条边恰好经过两次,因此一共将记录2n-1个结点,我们用E[1…2n-1]来表示这个数组,并用R[i]来表示E数组中第一个值为i的元素下标 LCA问题转化为RMQ问题 那么对于任何R[u]R[v]的结点u,v来说,DFS中从第一次访问u到第一次访问v所经过的结点的路径应该是E[R[u],…,R[v]] 虽然这些结点会包含u的后代，但是其中深度最小的一定是u和v的LCA 令数组L[i]表示E[i]的深度，那么当R[u]=R[v]时，LCA(T,u,v)=RMQ(L,R[u],R[v]) LCA问题转化为RMQ问题 类似的，如果R[u]R[v]，LCA(T,u,v)=RMQ(L,R[v],R[u]) 这样，在O(n)的时间内把LCA问题转化为RMQ问题 一般RMQ问题的ST算法 D[i,j]表示从i开始,长度为2^j的区间内的RMQ,则有递推式 D[i,j]=min{D[i,j-1],D[i+2^(j-1),j-1]} 这样,预处理的复杂度为O(nlogn) 询问时,只要取k=[log2(j-i+1)] RMQ(i,j)=min{D[i,k],D[j+1-2^k,k]} 总结 朴素的LCA算法每次询问的复杂度为O(n) 将LCA转化为RMQ问题，每次询问的复杂度为O(1),预处理的复杂度为O(nlogn) 还有一些算法,在此就不多作介绍,有兴趣的同学可以参考《算法艺术与信息学竞赛》(刘汝佳 黄亮) POJ1986 谢谢！ * * *