RMQ (Range Minimum/Maximum Query)算法

Myth丶恋晨 2022-08-07 12:36 45阅读 0赞

**1. 概述**

RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题，下面介绍一下解决这两种问题的比较高效的算法。当然，该问题也可以用线段树（也叫区间树）解决，算法复杂度为：O(N)~O(logN)，这里我们暂不介绍。

**2.RMQ算法**

对于该问题，最容易想到的解决方案是遍历，复杂度是O(n)。但当数据量非常大且查询很频繁时，该算法无法在有效的时间内查询出正解。

本节介绍了一种比较高效的在线算法（ST算法）解决这个问题。所谓在线算法，是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理，待信息充足以后便可以用较少的时间回答每个查询。ST（Sparse Table）算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。

**（一）首先是预处理，用动态规划（DP）解决。**

设A\[i\]是要求区间最值的数列，F\[i, j\]表示从第i个数起连续2^j个数中的最大值。（DP的状态）

例如：

A数列为：3 2 4 5 6 8 1 2 9 7

F\[1，0\]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。同理 F\[1,1\] = max(3,2) = 3, F\[1，2\]=max(3,2,4,5) = 5，F\[1，3\] = max(3,2,4,5,6,8,1,2) = 8;

并且我们可以容易的看出F\[i,0\]就等于A\[i\]。（DP的初始值）

这样，DP的状态、初值都已经有了，剩下的就是状态转移方程。

我们把F\[i，j\]平均分成两段（因为f\[i，j\]一定是偶数个数字），从 i 到i + 2 ^ (j - 1) - 1为一段，i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1))。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。F\[i，j\]就是这两段各自最大值中的最大值。于是我们得到了状态转移方程F\[i, j\]=max（F\[i，j-1\], F\[i + 2^(j-1)，j-1\]）。

代码如下：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  **void** RMQ(**int** num) //预处理->O(nlogn)  
2.  \{  
3.      **for**(**int** j = 1; j < 20; ++j)  
4.          **for**(**int** i = 1; i <= num; ++i)  
5.              **if**(i + (1 << j) - 1 <= num)  
6.              \{  
7.                  maxsum\[i\]\[j\] = max(maxsum\[i\]\[j - 1\], maxsum\[i + (1 << (j - 1))\]\[j - 1\]);  
8.                  minsum\[i\]\[j\] = min(minsum\[i\]\[j - 1\], minsum\[i + (1 << (j - 1))\]\[j - 1\]);  
9.              \}  
10. \}

这里我们需要注意的是循环的顺序，我们发现外层是j，内层所i，这是为什么呢？可以是i在外，j在内吗？

答案是不可以。因为我们需要理解这个状态转移方程的意义。

状态转移方程的含义是：先更新所有长度为F\[i,0\]即1个元素，然后通过2个1个元素的最值，获得所有长度为F\[i,1\]即2个元素的最值，然后再通过2个2个元素的最值，获得所有长度为F\[i,2\]即4个元素的最值，以此类推更新所有长度的最值。

而如果是i在外，j在内的话，我们更新的顺序就是F\[1,0\],F\[1,1\],F\[1,2\],F\[1,3\],表示更新从1开始1个元素，2个元素，4个元素，8个元素（A\[0\],A\[1\],....A\[7\]）的最值，这里F\[1,3\] = max(max(A\[0\],A\[1\],A\[2\],A\[3\]),max(A\[4\],A\[5\],A\[6\],A\[7\]))的值，但是我们根本没有计算max(A\[0\],A\[1\],A\[2\],A\[3\])和max(A\[4\],A\[5\],A\[6\],A\[7\])，所以这样的方法肯定是错误的。

为了避免这样的错误，一定要好好理解这个状态转移方程所代表的含义。

**（二）然后是查询。**

假如我们需要查询的区间为(i,j)，那么我们需要找到覆盖这个闭区间(左边界取i，右边界取j)的最小幂（可以重复，比如查询5，6，7，8，9，我们可以查询5678和6789）。

因为这个区间的长度为j - i + 1,所以我们可以取k=log2( j - i + 1)，则有：RMQ(A, i, j)=max\{F\[i , k\], F\[ j - 2 ^ k + 1, k\]\}。

举例说明，要求区间\[2，8\]的最大值，k = log2（8 - 2 + 1）= 2，即求max(F\[2, 2\]，F\[8 - 2 ^ 2 + 1, 2\]) = max(F\[2, 2\]，F\[5, 2\])；

在这里我们也需要注意一个地方，就是<<运算符和+-运算符的优先级。

比如这个表达式：5 - 1 << 2是多少？

答案是：4 \* 2 \* 2 = 16。所以我们要写成5 - (1 << 2)才是5-1 \* 2 \* 2 = 1。

[view plain]: http://blog.csdn.net/niushuai666/article/details/6624672#