RMQ LCA

第一节 RMQ、LCA概述

      LCA:Lowest Common Ancestor，译为最近公共祖先。其解释就是说：在有根树中，找出树中任意两个节点最近的公共祖先，或者说找到任意两个节点离树根最远的公共祖先。

       RMQ：Range Minimum Query，译为区间最小值查询。其解释就是说：对于含有N个元素的数列A，在数列中找到两个指定索引之间的最小值及最小值的位置。

第二节 RMQ Algorithm

   首先我们来看RQM算法，我将会根据预处理和查询的速度介绍几种解决该问题的方法。
  设有数组A[N]，其表示如下：

 要求求得区间(2,7)的最小元素，如下图所示：

解法一：Sparse Table(ST) algorithm
     ST算法是一种比较高效的在线处理RMQ问题的算法，所谓在线算法，是指每输入一个查询就会马上处理这个查询。ST算法首先会对序列做预处理，完成之后就可以对查询做回答了。
    分析：
            预处理：O(N * LogN)。
            查询：O(1)，这样的查询正是我们想要的。
  算法流程：
预处理：首先用维护一个数组M[N][LogN]，M[i][j]的值是从原序列A的i位置开始，连续2j 个元素的最小值的下标，如下所示：

           

 那么，我们如何计算M[i][j]呢？
    我们采用DP的思想将区间分成两部分，即M[i][j - 1]和M[i][2^(j - 1)]。现在我们只需比较这两个子区间就可以得到M[i][j]了。比较规则如下：

                     

 于是乎，就可按照此写出代码：

void Proprocessing(int M[N][logN], int *A, int N){int i, j;for(j = 1; (1 << j) < N; j++){for(i = 0; (i + (1 << j) - 1) < N; i++){if(A[ M[i][j - 1] ] < A[ M[i + (1 << (j - 1))][i - 1]]){M[i][j] = M[i][j - 1];}else{M[i][j] = A[ M[i + (1 << (j - 1))][i - 1]];}}} }

​​​​​
https://blog.csdn.net/fengchaokobe/article/details/8104784#
​​     https://blog.csdn.net/blaze003003/article/details/81084954

总结

以上是生活随笔为你收集整理的RMQ LCA的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。