LCA RMQ求解最小公共祖先问题

《LCA RMQ求解最小公共祖先问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、LCARMQ求解最小公共祖先问题LCA,RMQ,祖先,求解以下文字转自中山大学逸仙时空BBS算法版  (1)  /(2)  (7)/    (3)(4)  (8)  /  (5)  (6)一个nlogn预处理，O(1)查询的算法.Step1:      按先序遍历整棵树，记下两个信息:结点访问顺序和结点深度.      如上图:      结点访问顺序是:123245464217871//共2n-1个值      结点对应深度是:012123232101210Step2:      如果查询结点3与结点6的公共祖先,则

2、考虑在访问顺序中      3第一次出现，到6第一次出现的子序列:324546.      这显然是由结点3到结点6的一条路径.      在这条路径中，深度最小的就是最近公共祖先(LCA).即      结点2是3和6的LCA.Step3:      于是问题转化为,给定一个数组R,及两个数字i,j,如何找出      数组R中从i位置到j位置的最小值..      如上例,就是R[]={0,1,2,1,2,3,2,3,2,1,0,1,2,1,0}.      i=2;j=7;      这个问题就是经典的RMQ问题.   

3、   这里介绍一个比较简单的方法O(nlogn)预处理，O(1)回答每个询问.      RMQ问题的预处理:      用一个数组d[j]表示数组R中，从i位置到i+2^j-1位置的最小值.      这个d[j]很容易dp得到.      d[j+1]=min{d[j],d[i+2^j][j]};      空间:O(nlogn)时间:O(nlogn).Step4:      询问:      如果询问:从a到b里面最小的值..主要思路找两个长度是2^k的区间:      [a,a+2^k-1]及[b-1-2^k,b]把区

4、间[a,b]覆盖掉.这很容易做到的,      只要:2^k*2>=

5、b-a

6、.      于是a到b里面的最小值=min{d[a][k],d[b-2^k-1][k]}关于RMQ的ST算法SparseTable(ST)algorithmAbetterapproachistopreprocessRMQforsubarraysoflength2kusingdynamicprogramming.WewillkeepanarrayM[0,N-1][0,logN]whereM[j]istheindexoftheminimumvaluei

7、nthesubarraystartingatihavinglength2j.Hereisanexample:ForcomputingM[j]wemustsearchfortheminimumvalueinthefirstandsecondhalfoftheinterval.It'sobviousthatthesmallpieceshave2j-1length,sotherecurrenceis:Thepreprocessingfunctionwilllooksomethinglikethis:voidprocess2(intM

8、[MAXN][LOGMAXN],intA[MAXN],intN){inti,j;//initializeMfortheintervalswithlength1for(i=0;i

9、1];}下面给出LCA问题向RMQ问题的转化方法。对树进行深度优先遍历，每当“进入”或回溯到某个结点时，将这个结点的深度存入数组E最后一位。同时记录结点i在数组中第一次出现的位置(事实上就是进入结点i时记录的位置)，记做R。如果结点E的深度记做D，易见，这时求LCA(T,u,v)，就等价于求E[RMQ(D,R,R[v])]，(R

10、D,R[2],R[5])]=E[RMQ(D,2,7)]=E[3]=1LCA(T,3,4)=E[RMQ(D,R[3],R[4])]=E[RMQ(D,4,5)]=E[4]=3LCA(T,4,5)=E[RMQ(D,R[4],R[5])]=E[RMQ(D,5,7)]=E[6]=3易知