学习RMQ的一些感悟和理解

　　由于数据结构期末考的最后一题扯到了LCA问题，当时把有段时间没刷题的我吓坏了，还以为要写一个对于图的LCA，生怕写错了，仔细一看原来是个顺序表下的二叉树的最近公共祖先，似乎不是很难啊，特判一下再一直除以二不就好了吗……。

　　考完突然想起来关于LCA的有两大算法，离线Tarjan和在线ST倍增，其中前者除非是题目已经直接或间接给定了关于两点的询问，否则像我这样建Gragh边又建Query边再去Tarjan的算法实在不适合在线的情况，然后又感慨了一下若期末考就是叫我求树上的LCA，那我还写一个Tarjan？不说还能记得多少……卷面都写炸了，还好弱校数据结构考试不会这么变态。

好了废话讲完了，下面开始正题

RMQ一般是一个二维数组，用$dp[i][j]$表示起点为i开始连续数$2^j$个元素其中的最值，由于对于一个闭区间有：$R-L+1=len$因此也可以用另外一种记法：闭区间为$[i,i+2^j-1]$内的最值。个人感觉后者可能更有助于代码的理解和手写。

然后就是预处理的步骤，显然元数组可以用来初始化$dp[i][0]$，然后剩下的用循环来处理，此时也许不知道具体代码怎么写，但是一定可以想到如果我知道了一个区间的左边半个dp和右边半个dp，那么这个区间的dp就知道了，因此我们要一层一层地增加这个“半个”的长度，所以循环顺序是j在外i在内，不理解的话自己写一下手推 的过程就知道了。

以前感觉RMQ不好用因为对于区间的边界处理完全不懂，如果数组下标从0开始我估计就不会了，现在可以用上面的话来得到dp方程：$dp[i][j]=max(dp[i][j-1], dp[i+(1<<(j-1))][j-1])$，即闭区间$[i,i+2^j-1]$被分为左半部分$[i, i+2^{j-1}-1]$与右半部分$[i+2^{j-1}, i+2^j-1]$。

区间预处理结束后还有个区间最值查询，步骤是把区间最接近的$2^k$长度，然后在$[l, l+2^k]$与$[r-2^k+1, r]$取最值，自己试着推一下就可以发现这样既不会超出区间长度又不会不能覆盖区间。

下面给出我自己总结的RMQ-ST模版，感觉在理解区间边界的情况下很容易写出来，挺好用的

void RMQ_init(int l, int r)
{
    int i, j;
    for (i = l; i <= r; ++i)
        maxm[i][0] = minm[i][0] = cow[i];
    for (j = 1; l + (1 << j) - 1 <= r; ++j)
    {
        for (i = l; i + (1 << j) - 1 <= r; ++i)
        {
            dp[i][j] = max<int>(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int ST(int l, int r)
{
    int k = log2(r - l + 1);
    return max<int>(maxm[l][k], maxm[r - (1 << k) + 1][k]);
}

学习RMQ的一些感悟和理解

原文：http://www.cnblogs.com/Blackops/p/6295094.html