RMQ and LCA

2020年08月13日 阅读数:44
这篇文章主要向大家介绍RMQ and LCA,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
                                        Range Minimum Query and Lowest Common Ancestor

    【原文见  http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestorphp

                                                                                                                 做者:      By danielp
                                                                                                                    Topcoder  Member
                                                                                                                翻译:      农夫三拳@seu
Introduction
  Notations
  Range Minimum Query (RMQ)
      Trivial algorithms for RMQ
      A <O(N), O(sqrt(N))> solution
      Sparse Table (ST) algorithm
      Segment Trees
  Lowest Common Ancestor (LCA)
      A <O(N), O(sqrt(N))> solution
      Another easy solution in <O(N logN, O(logN)>
      Reduction from LCA to RMQ
  From RMQ to LCA
  An <O(N), O(1)> algorithm for the restricted RMQ
  Conclusion  

Introduction

      在一棵树中查找一对结点的最近公共祖先(LCA)的问题在20世纪末期已经被仔细的研究过了,而且它如今已经成为算法中图论的基本算法了。这个问题之因此有趣并非由于处理它的算法颇有技巧,而是由于它在字符串处理和生物学计算中的普遍应用,例如,当LCA和后缀树或者其余树形结构在一块儿使用时。Harel and Tarjan是首先深刻研究这个问题的人,他们得出:在对输入树LCA进行线性处理后,查询能够在常数时间内获得答案。他们的工做已经获得了普遍的延伸,这篇教程将展现一些有趣的方法,而它们还也能够用在其余的问题上。
html


      让咱们考虑一个不太抽象的LCA的例子:生命树。地球上当前的居住者是由其余物种进化而来已是一个不争的事实。这种进化结构能够表示成一棵树,其中节点表示物种,而它的孩子结点表示从该物种直接进化获得的物种。如今经过在树中查找一些结点的LCA把具备类似特征的物种划分红组,咱们能够找出两个物种共同的祖先,而且咱们能够知道它们所拥有的类似特征是来自于那个祖先。
node

      Range Minimum Query(RMQ)被用在数组中用来查找两个指定索引中具备最小值的元素的位置。咱们后面将会看到LCA问题能够归约成一个带限制的RMQ问题,其中相邻的数组元素相差1。程序员

      尽管如此, RMQ并非仅仅和LCA一块儿用的。当他们在和后缀数组(一个新的数据结构,它支持和后缀树同等效率的字符串查询,可是使用更少的内存且编码很简单)一块儿使用时,在字符串处理中扮演着至关重要的角色。算法

      在这篇教程中,咱们将首先讨论RMQ。咱们将给出解决这个问题的多种方法--有一些速度比较慢可是容易编码,而其余的则更快。在第二部分咱们将讨论LCA和RMQ之间的关系。首先咱们先回顾一下不使用RMQ来解决LCA的两个简单方法;而后咱们将指出RMQ和LCA问题实际上是等价的;而且,最后,咱们将看到RMQ问题怎样规约成它的限制版本,而且对于这个特殊状况给出一个最快的算法。数组


Notations
      假设一个算法预处理时间为 f(n),查询时间为g(n)。这个算法复杂度的标记为<f(n), g(n)>。咱们将用RMQA(i, j)来表示数组中索引i和j之间最小值的位置。 uv的离树T根结点最远的公共祖先用LCAT(u, v)表示。

Range Minimum Query(RMQ)
      给定数组A[0, N-1]找出给定的两个索引间的最小值的位置。

数据结构



Trivial algorithms for RMQ

       对每一对索引(i, j),将RMQA(i, j)存储在M[0, N-1][0, N-1]表中。普通的计算将获得一个<O(N3), O(1)> 复杂度的算法。尽管如此,经过使用一个简单的动态规划方法,咱们能够将复杂度下降到<O(N2), O(1)>。预处理的函数和下面差很少:ide

  
  
void process1(int M[MAXN][MAXN], int A[MAXN], int  N)
{
      
int
 i, j;
    
for (i =0; i < N; i++
)
        M[i][i] 
=
 i;
    
for (i = 0; i < N; i++
)
        
for (j = i + 1; j < N; j++
)
            
if (A[M[i][j - 1]] <
 A[j])
                M[i][j] 
= M[i][j - 1
];
            
else

                M[i][j] 
= j;
}
这个普通的算法至关的慢而且使用 O(N2)的空间,对于大数据它是没法工做的。


An <O(N), O(sqrt(N))> solution

  一个比较有趣的点子是把向量分割成sqrt(N)大小的段。咱们将在M[0,sqrt(N)-1]为每个段保存最小值的位置。
M能够很容易的在O(N)时间内预处理。下面是一个例子:

函数


       如今让咱们看看怎样计算RMQA(i, j)。想法是遍历全部在区间中的sqrt(N)段的最小值,而且和区间相交的前半和后半部分。为了计算上图中的RMQA(2,7),咱们应该比较A[2]A[M[1]]A[6] 和A[7],而且得到最小值的位置。能够很容易的看出这个算法每一次查询不会超过3 * sqrt(N)次操做。post

      这个方法最大的有点是可以快速的编码(对于TopCoder类型的比赛),而且你能够把它改为问题的动态版本(你能够在查询中间改变元素)。

Sparse Table (ST) algorithm    

     一个更好的方法预处理RMQ 是对2k 的长度的子数组进行动态规划。咱们将使用数组M[0, N-1][0, logN]进行保存,其中M[i][j]是以i 开始,长度为 2j的子数组的最小值的索引。下面是一个例子



为了计算M[i][j]咱们必须找到前半段区间和后半段区间的最小值。很明显小的片断有这2j - 1 长度,所以递归以下:


预处理的函数以下:
  
  
void process2(int M[MAXN][LOGMAXN], int A[MAXN], int  N)
  
{
      
int
 i, j;
   
  
//initialize M for the intervals with length 1

      for (i = 0; i < N; i++)
          M[i][
0=
 i;
  
//compute values from smaller to bigger intervals

      for (j = 11 << j <= N; j++)
          
for (i = 0; i + (1 << j) - 1 < N; i++
)
              
if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1
]])
                  M[i][j] 
= M[i][j - 1
];
              
else

                  M[i][j] 
= M[i + (1 << (j - 1))][j - 1];
  }
  

一旦咱们预处理了这些值,让咱们看看怎样使用它们去计算RMQA(i, j)。思路是选择两个可以彻底覆盖区间[i..j]的块而且找到它们之间的最小值。设k = [log(j - i + 1)].。为了计算RMQA(i, j) 咱们可使用下面的公式



So, the overall complexity of the algorithm is <O(N logN), O(1)>

Segment trees

     为了解决RMQ问题咱们也可使用线段树。线段树是一个相似堆的数据结构,能够在基于区间数组上用对数时间进行更新和查询操做。咱们用下面递归方式来定义线段树的[i, j]区间:

  • 第一个结点将保存区间[i, j]区间的信息
  • 若是i<j 左右的孩子结点将保存区间[i, (i+j)/2][(i+j)/2+1, j] 的信息

      注意具备N个区间元素的线段树的高度为[logN] + 1。下面是区间[0,9]的线段树:




线段树和堆具备相同的结构,所以咱们定义x是一个非叶结点,那么左孩子结点为2*x,而右孩子结点为2*x+1

 使用线段树解决RMQ问题,咱们应该使用数组 M[1, 2 * 2[logN] + 1],这里M[i]保存结点i区间最小值的位置。初始时M的全部元素为-1。树应当用下面的函数进行初始化(be是当前区间的范围):

  

  
  
void initialize(int node, int b, int e, int M[MAXIND], int A[MAXN], int  N)
{
if (b ==
 e)
M[node] 
=
 b;
    
else

     
{
//compute the values in the left and right subtrees

        initialize(2 * node, b, (b + e) / 2, M, A, N);
        initialize(
2 * node + 1, (b + e) / 2 + 1
, e, M, A, N);
//
search for the minimum value in the first and
//second half of the interval

        if (A[M[2 * node]] <= A[M[2 * node + 1]])
            M[node] 
= M[2 *
 node];
        
else

            M[node] 
= M[2 * node + 1];
    }

}

      上面的函数映射出了这棵树建造的方式。当计算一些区间的最小值位置时,咱们应当首先查看子结点的值。调用函数的时候使用 node = 1b = 0e  = N-1

      如今咱们能够开始进行查询了。若是咱们想要查找区间[i, j]中的最小值的位置时,咱们可使用下一个简单的函数:

  
  
  int query(int node, int b, int e, int M[MAXIND], int A[MAXN], int i, int  j)
{
int
 p1, p2;
 
 
//
if the current interval doesn't intersect
//the query interval return -1

    if (i > e || j < b)
        
return -1
;
 
//
if the current interval is included in
//the query interval return M[node]

    if (b >= i && e <= j)
        
return
 M[node];
 
//
compute the minimum position in the
//left and right part of the interval

    p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
    p2 
= query(2 * node + 1, (b + e) / 2 + 1
, e, M, A, i, j);
 
//
return the position where the overall
//minimum is

    if (p1 == -1)
        
return M[node] =
 p2;
    
if (p2 == -1
)
        
return M[node] =
 p1;
    
if (A[p1] <=
 A[p2])
        
return M[node] =
 p1;
    
return M[node] =
 p2;
 
}

     你应该使用node = 1b = 0e = N - 1来调用这个函数,由于分配给第一个结点的区间是[0, N-1]

     能够很容易的看出任何查询均可以在O(log N)内完成。注意当咱们碰到完整的in/out区间时咱们中止了,所以数中的路径最多分裂一次。用线段树咱们得到了<O(N), O(logN)>的算法。线段树很是强大,不只仅是由于它可以用在RMQ上,

还由于它是一个很是灵活的数据结构,它可以解决动态版本的RMQ问题和大量的区间搜索问题。

Lowest Common Ancestor (LCA)

      给定一棵树T和两个节点uv,找出uv的离根节点最远的公共祖先。下面是一个例子(这篇教程中全部的例子中树的根结点均为1):




An <O(N), O(sqrt(N))> solution     

      将输入分红同等大小的部分来解决RMQ问题是一个颇有趣的方法。这个方法对LCA问题一样适用。大体思想是将树分红sqrt(H)个部分,其中H是树的高度。所以第一个段将包含0sqrt(H)-1层,第二个段则包含sqrt(H)2*sqrt(H)-1层,依次下去。下面给出了样例中的树是如何被分割的:



      如今,对于每个结点,咱们应该知道每个段的在上一层中的祖先。咱们将预处理这些值,并将他们存储在P[1, MAXN]中。下面是对于样例中的树的P数组内容(为了简化,对于在第一个段中的全部结点i,P[i]=1):



      注意对于每个段中的上面一部分,P[i]=T[i]。咱们可使用深度优先搜索对P进行预处理(T[i]是树中i结点的父亲结点,nr[sqrt(H)]L[i]是结点i所处的层的编号):

  

  
  
void dfs(int node, int T[MAXN], int N, int P[MAXN], int L[MAXN], int nr)   {
int
 k;
 
//
if node is situated in the first
//
section then P[node] = 1
//
if node is situated at the beginning
//
of some section then P[node] = T[node]
//
if none of those two cases occurs, then
//P[node] = P[T[node]]

if (L[node] < nr)
         P[node] 
= 1
;
else

        
if(!(L[node] % nr))
              P[node] 
=
 T[node];
        
else

              P[node] 
= P[T[node]];
 
for
 each son k of node
      dfs(k, T, N, P, L, nr);
}

 如今,咱们能够很容易的进行查询了。为了找到LCA(x,y),咱们首先找出它所在的段,而后再用普通的方法计算它。下面是代码:

  
  
 int LCA(int T[MAXN], int P[MAXN], int L[MAXN], int x, int  y)
{
//
as long as the node in the next section of
//
x and y is not one common ancestor
//
we get the node situated on the smaller
//lever closer

    while (P[x] != P[y])
          
if (L[x] >
 L[y])
=
 P[x];
          
else

                y 
= P[y];
          
//now they are in the same section, so we trivially compute the LCA

while (x != y)
          
if (L[x] >
 L[y])
             x 
=
 T[x];
          
else

             y 
= T[y];
      
return
 x;
}

      这个函数最多执行2 * sqrt(H)次操做。经过使用这个方法,咱们获得了<O(N), O(sqrt(H))>的算法,这里H指的是树的高度。在最坏的状况下H=N,所以总的复杂度为<O(N), O(sqrt(N))>。这个算法的主要好处是易于编码(Division1中的程序员应该在15分钟内完成这段代码)。

Another easy solution in <O(N logN, O(logN)>

    若是咱们对这个须要一个更快的解决方法,咱们可使用动态规划。首先咱们构建一张表P[1,N][1,logN],这里P[i][j]指的是结点i的第2j个祖先。为了计算这个值,咱们可使用下面的递归:
 



预处理的函数以下:
 void process3(int N, int T[MAXN], int  P[MAXN][LOGMAXN])
{
    
int
 i, j;
 
//we initialize every element in P with -1

    for (i = 0; i < N; i++)
        
for (j = 01 << j < N; j++
)
            P[i][j] 
= -1
;
 
//the first ancestor of every node i is T[i]

    for (i = 0; i < N; i++)
        P[i][
0=
 T[i];
 
//bottom up dynamic programing

for (j = 11 << j < N; j++)
       
for (i = 0; i < N; i++
)
           
if (P[i][j - 1!= -1
)
P[i][j] 
= P[P[i][j - 1]][j - 1
];
}

这个过程将花费O(N logN) 的时间和空间。如今让咱们看看如何查询。用L[i]来表示节点i在树中所处的层数。能够看到,若是pq在树中的同一层中,咱们可使用一个类二分查找的方法进行搜索。所以,对于2j次方(界于log[L[p]0之间,降序),若是P[p][j] != P[q][j] ,那么能够知道LCA(p, q)必然在更高的层中,所以咱们继续搜索LCA(p = P[p][j], q = P[q][j])。最后,pq都有了相同的祖先,所以返回T[p]。让咱们看看若是L[p] != L[q]的状况。 不妨假设L[p] < L[q]。咱们可使用相似的二分搜索方法来查找与q在同一层次的p的祖先,而后咱们在用下面所描述的方法计算LCA。整个函数以下:



  
  
int query(int N, int P[MAXN][LOGMAXN], int  T[MAXN],
int L[MAXN], int p, int
 q)
{
    
int
 tmp, log, i;
 
//if p is situated on a higher level than q then we swap them

if (L[p] < L[q])
tmp 
= p, p = q, q =
 tmp;
//we compute the value of [log(L[p)]

    for (log = 11 << log <= L[p]; log++);
    log
--
;
 
//
we find the ancestor of node p situated on the same level
//with q using the values in P

    for (i = log; i >= 0; i--)
        
if (L[p] - (1 << i) >=
 L[q])
            p 
=
 P[p][i];
 
    
if (p ==
 q)
        
return
 p;
 
//we compute LCA(p, q) using the values in P

for (i = log; i >= 0; i--)
        
if (P[p][i] != -1 && P[p][i] !=
 P[q][i])
            p 
= P[p][i], q =
 P[q][i];
 
    
return
 T[p];
}

  

      如今,咱们能够看到这个函数最多须要执行2*log(H)次的操做,这里的H是树的高度。在最坏状况下H=N,所以总的时间复杂度为<O(NlogN),O(logN)>。这个方案很是易编码,而且它比前一个要快。

Reduction from LCA to RMQ

     如今,让咱们看看怎样用RMQ来计算LCA查询。事实上,咱们能够在线性时间里将LCA问题规约到RMQ问题,所以每个解决RMQ的问题均可以解决LCA问题。让咱们经过例子来讲明怎么规约的:




                                                                    点击放大图片
      注意LCAT(u, v)是在对T进行dfs过程中在访问uv之间离根结点最近的点。所以咱们能够考虑树的欧拉环游过程uv之间全部的结点,并找到它们之间处于最低层的结点。为了达到这个目的,咱们能够创建三个数组:

E[1, 2*N-1]  - 对T进行欧拉环游过程当中全部访问到的结点;E[i]是在环游过程当中第i个访问的结点
L[1,2*N-1] -  欧拉环游中访问到的结点所处的层数;L[i]E[i]所在的层数
H[1, N] - H[i] E中结点i第一次出现的下标(任何出现i的地方都行,固然选第一个不会错)

    假定H[u]<H[v](不然你要交换uv)。能够很容易的看到uv第一次出现的结点是E[H[u]..H[v]]。现

在,咱们须要找到这些结点中的最低层。为了达到这个目的,咱们可使用RMQ。所以 LCAT(u, v) = E[RMQL(H[u], H[v])] (记住RMQ返回的是索引),下面是E,L,H数组:


点击放大图片


注意L中连续的元素相差为1。

From RMQ to LCA
      咱们已经看到了LCA问题能够在线性时间规约到RMQ问题。如今让咱们来看看怎样把RMQ问题规约到LCA。这个意味着咱们实际上能够把通常的RMQ问题规约到带约束的RMQ问题(这里相邻的元素相差1)。为了达到这个目的,咱们须要使用笛卡尔树。
      对于数组A[0,N-1]的笛卡尔树C(A)是一个二叉树,根节点是A的最小元素,假设iA数组中最小元素的位置。当i>0时,这个笛卡尔树的左子结点是A[0,i-1]构成的笛卡尔树,其余状况没有左子结点。右结点相似的用A[i+1,N-1]定义。注意对于具备相同元素的数组A,笛卡尔树并不惟一。在这篇教程中,将会使用第一次出现的最小值,所以笛卡尔树看做惟一。能够很容易的看到RMQA(i, j) = LCAC(i, j)
下面是一个例子:





如今咱们须要作的仅仅是用线性时间计算C(A)。这个可使用栈来实现。初始栈为空。而后咱们在栈中插入A的元素。在第i步,A[i]将会紧挨着栈中比A[i]小或者相等的元素插入,而且全部较大的元素将会被移除。在插入结束以前栈中A[i]位置前的元素将成为i的左儿子,A[i]将会成为它以后一个较小元素的右儿子。在每一步中,栈中的第一个元素老是笛卡尔树的根。
若是使用栈来保存元素的索引而不是值,咱们能够很轻松的创建树。下面是上述例子中每一步栈的状态:

Step Stack Modifications made in the tree
0 0 0 is the only node in the tree.
1 0 1 1 is added at the end of the stack. Now, 1 is the right son of 0.
2 0 2 2 is added next to 0, and 1 is removed (A[2] < A[1]). Now, 2 is the right son of 0 and the left son of 2 is 1.
3 3 A[3] is the smallest element in the vector so far, so all elements in the stack will be removed and 3 will become the root of the tree. The left child of 3 is 0.
4 3 4 4 is added next to 3, and the right son of 3 is 4.
5 3 4 5 5 is added next to 4, and the right son of 4 is 5.
6 3 4 5 6 6 is added next to 5, and the right son of 5 is 6.
7 3 4 5 6 7 7 is added next to 6, and the right son of 6 is 7.
8 3 8 8 is added next to 3, and all greater elements are removed. 8 is now the right child of 3 and the left child of 8 is 4.
9 3 8 9 9 is added next to 8, and the right son of 8 is 9.

     注意A中的每一个元素最多被增长一次和最多被移除一次。所以上述算法的时间复杂度为O(N)。下面是树的处理函数:


  
  
void computeTree(int A[MAXN], int N, int  T[MAXN])
 
{
    
int st[MAXN], i, k, top = -1
;
 
//
we start with an empty stack
//at step i we insert A[i] in the stack

    for (i = 0; i < N; i++)
    
{
//
compute the position of the first element that is
//equal or smaller than A[i]

        k = top;
        
while (k >= 0 && A[st[k]] >
 A[i])
            k
--
;
//we modify the tree as explained above

       if (k != -1)
            T[i] 
=
 st[k];
       
if (k <
 top)
            T[st[k 
+ 1]] =
 i;
//
we insert A[i] in the stack and remove
//any bigger elements

        st[++k] = i;
        top 
=
 k;
    }

//the first element in the stack is the root of
//the tree, so it has no father

    T[st[0]] = -1;
}

 
An<O(N), O(1)> algorithm for the restricted RMQ

      如今咱们知道了通常的RMQ问题可使用LCA归约成约束版本。这里,数组中相邻的元素差值为1.咱们可使用一个更快的<O(N), O(1)> 的算法。下面咱们将在数组A[0,N-1]上解决RMQ问题,这里|A[i]-A[i+1]|=1,i=[1,N-1]。咱们将把A转换为一个二元的有着N-1个元素的数组,其中A[i]=A[i]-A[i+1]。很显然A中的元素只有多是+1或者-1。注意原来的A[i]的值如今是A[1],A[2],...,A[i]的和加上原来的A[0]。尽管如此,下面咱们根本不须要原来的值。


      为了解决这个问题的约束版本,咱们须要将A分红l = [(log N) / 2]的大小块.让A'[i]A中第i块的最小值,B[i]A中最小块值的位置。A和B的长度均为N/l。如今咱们利用第一节中讨论的ST算法预处理A'数组。这个将花费O(N/l * log(N/l))=O(N)的时间和空间。通过预处理以后,咱们能够在O(1)时间内在不少块上进行查询。具体的查询过程和上面说过的同样。注意每一个块的长度为l=[(logN)/2],这个很是的小。一样,要注意A是一个二元数组。二元数组的总的元素的大小l知足2l=sqrt(N)。所以,对于每个二元数组中的块l,咱们须要在表P中查询每一对索引的RMQ。这个能够在O(sqrt(N)*l2)=O(N) 的时间和空间内解决。为了索引表P,能够预处理A中的每个块而且将其存储在数组T[1,N/l]中。块的类型能够成为一个二进制数若是把-1替换成0,把+1替换成1。

    如今,对于询问 RMQA(i, j) 咱们有两种状况:

  • ij在同一个块中,所以咱们使用在PT中计算的值 
  • ij在不一样的块中,所以咱们计算三个值:从ii所在块的末尾的PT中的最小值,全部ij中块中的经过与处理获得的最小值以及从j所在块ij在同一个块中,所以咱们使用在PT中计算的值jPT的最小值;最后咱们咱们只要计算三个值中最小值的位置便可。
    Conclusion
          RMQ和LCA是密切相关的问题,由于他们互相之间均可以规约。有许多算法能够用来解决它们,而且他们适应于一类问题。690

    下面是一些用来练习线段树,LCA和RMQ的题目:

    SRM 310 -> 
    Floating Median
    http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.pku.edu.cn/JudgeOnline/problem?id=1986&refer=
    http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.pku.edu.cn/JudgeOnline/problem?id=2374&refer=
    http://www.topcoder.com/tc?module=LinkTracking&link=http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2045&refer=
    http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.pku.edu.cn/JudgeOnline/problem?id=2763&refer=
    http://www.topcoder.com/tc?module=LinkTracking&link=http://www.spoj.pl/problems/QTREE2/&refer=
    http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.uva.es/p/v109/10938.html&refer=
    http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.sgu.ru/problem.php?contest=0%26problem=155&refer=


    References
    - "
    Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE" [PDF] by Johannes Fischer and Volker Heunn
    - "
    The LCA Problem Revisited" [PPT] by Michael A.Bender and Martin Farach-Colton - a very good presentation, ideal for quick learning of some LCA and RMQ aproaches
    - "
    Faster algorithms for finding lowest common ancestors in directed acyclic graphs" [PDF] by Artur Czumaj, Miroslav Kowaluk and Andrzej Lingas