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

LCA RMQ求解最小公共祖先问题LCA, RMQ, 祖先, 求解以下文字转自中山大学逸仙时空BBS算法版 (1) / (2) (7)/ (3) (4) (8) / (5) (6)一个nlogn 预处理，O(1)查询的算法. Step 1: 按先序遍历整棵树，记下两个信息:结点访问顺序和结点深度. 如上图: 结点访问顺序是: 1 2 3 2 4 5 4 6 4 2 1 7 8 7 1 /共2n-1个值 结点对应深度是: 0 1 2 1 2 3 2 3 2 1 0 1 2 1 0Step 2: 如果查询结点3与结点6的公共祖先,则考虑在访问顺序中 3第一次出现，到6第一次出现的子序列: 3 2 4 5 4 6. 这显然是由结点3到结点6的一条路径. 在这条路径中，深度最小的就是最近公共祖先(LCA). 即 结点2是3和6的LCA.Step 3: 于是问题转化为, 给定一个数组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问题. 这里介绍一个比较简单的方法O(nlogn)预处理，O(1)回答每个询问. RMQ问题的预处理: 用一个数组dj表示数组R中，从i位置到i+2j-1位置的最小值. 这个dj很容易dp得到. dj+1=mindj,di+2jj; 空间: O(nlogn) 时间: O(nlogn).Step 4: 询问: 如果询问:从a到b里面最小的值.主要思路找两个长度是2k的区间: a,a+2k-1及b-1-2k,b把区间a,b覆盖掉. 这很容易做到的, 只要: 2k*2= |b-a|. 于是a到b里面的最小值 = min dak,db-2k-1k 关于RMQ的ST算法Sparse Table (ST) algorithmA better approach is to preprocess RMQ for sub arrays of length 2k using dynamic programming. We will keep an array M0, N-10, logN where Mj is the index of the minimum value in the sub array starting at i having length 2j. Here is an example: For computing Mj we must search for the minimum value in the first and second half of the interval. Its obvious that the small pieces have 2j - 1 length, so the recurrence is: The preprocessing function will look something like this:void process2(int MMAXNLOGMAXN, int AMAXN, int N) int i, j; /initialize M for the intervals with length 1 for (i = 0; i N; i+) M0 = i;/compute values from smaller to bigger intervals for (j = 1; 1 j = N; j+) for (i = 0; i + (1 j) - 1 N; i+) if (AMj - 1 AMi + (1 (j - 1)j - 1) Mj = Mj - 1; else Mj = Mi + (1 (j - 1)j - 1; 下面给出LCA问题向RMQ问题的转化方法。 对树进行深度优先遍历，每当“进入”或回溯到某个结点时，将这个结点的深度存入数组E最后一位。同时记录结点i在数组中第一次出现的位置(事实上就是进入结点i时记录的位置)，记做R。如果结点E的深度记做D，易见，这时求LCA(T,u,v)，就等价于求ERMQ(D,R,Rv)，(RRv)。例如，对于第一节的例一，求解步骤如下：数列E为：1,2,1,3,4,3,5,3,1R为：1,2,4,5,7D为：0,1,0,1,2,1,2,1,0于是有：LCA(T,5,2) = ERMQ(D,R2,R5) = ERMQ(D,2,7) = E3 = 1LCA(T,3,4) = ERMQ(D,R3,R4) = ERMQ(D,4,5) = E