RMQ算法讲解

落日映苍穹つ 2022-05-27 04:40 244阅读 0赞

现在给你一个问题：给你一个数组 ，其中有N个数字，现在给你一次询问，给你区间\[l ，r\]，问你在这个区间内的最大值为多少?

哇！这题简单啊，一个for循环，遍历数组记录最大值输出即可啊。

那好，现在我告诉你假设N为50000，给你Q次询问（(1 ≤ *Q* ≤ 200,000)）,如果这种情况，我们还每次都进行暴力遍历求解的话，这时算法耗时就会很长。

![20180411183212554][]

是的，这种暴力遍历求解虽然思维简单，代码简短，但是很慢啊。

那该怎么做呢？这时候就需要RMQ算法来解决这个问题

**RMQ**（Range Minimum/Maximum Query），**即区间最值查询**。RMQ算法一般用较长时间做预处理，时间复杂度为O(nlogn)，然后可以在O（1）的时间内处理每次查询。

下面我们从一个实际问题来解释RMQ

我们假设数组arr为：1，2，6，8，4，3，7

我们设二维数组dp\[i\]\[j\]表示从第i位开始连续 ![2^j][2_j] 个数中的最小值。例如dp\[2\]\[1\]就表示从第二位数开始连续两个数的最小值（也就是从第二位数到第三位数的最小值），即2，6中的最小值，所以dp\[2\]\[1\] = 2;

其实我们求 dp\[i\]\[j\] 的时候可以把它分成两部分，第一部分是从 ![i][] 到 ![i+2^\{j-1\}-1][i_2_j-1_-1] ，第二部分从![i+2^\{j-1\}][i_2_j-1]到![i+2^j-1][i_2_j-1 1] ，为什么可以这么分呢？其实我们都知道二进制数前一个数是后一个的两倍，那么可以把 ![i][] 到 ![i+2^j-1][i_2_j-1 1] 这个区间通过![2^\{j-1\}][2_j-1]分成相等的两部分， 那么转移方程很容易就写出来了。（**dp\[i\]\[0\]就表示第i个数字本身）**

**dp\[i\]\[j\] = min(dp \[i\]\[j - 1\], dp \[i + (1 << j - 1)\]\[j - 1\])**

由此给出下列代码：

void rmq_init()
    {
        for(int i=1;i<=N;i++)
            dp[i][0]=arr[i];//初始化
        for(int j=1;(1<<j)<=N;j++)
            for(int i=1;i+(1<<j)-1<=N;i++)
                dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
    }

这里需要注意一个循环变量的顺序，我们看到外层循环变量为j，内层循环变量为i，这是为什么呢？可以互换一下位置吗？

答案当然是**不可以，**我们要理解这个状态转移方程的意义，这个状态方程的含义是：先更新每两个元素中的最小值，然后通过每两个元素的最小值获得每4个元素中的最小值，依次类推更新所有长度的最小值。

而如果是i在外，j在内的话，我们更新的顺序就变成了从1开始的前1个元素，前2个元素，前4个元素，前8个元素。。。

当j等于3的时候dp\[1\]\[3\] = min(min(ans\[0\],ans\[1\],ans\[2\],ans\[3\]),min(ans\[4\],ans\[5\],ans\[6\],ans\[7\])))的值，

但是我们根本没有计算min(ans\[0\],ans\[1\],ans\[2\],ans\[3\])和min(ans\[4\],ans\[5\],ans\[6\],ans\[7\])，所以这样的方法肯定是错误的。

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

**接下来我们来讲解RMQ的查询部分**，假设我们需要查询区间\[l ，r\]中的最小值，**令k = ![log\_2(r-l+1)][log_2_r-l_1]** ， 则区间\[l, r\]的最小值RMQ\[l,r\] = min(dp\[l\]\[k\], dp\[r - (1 << k) + 1\]\[k\]);

但是为什么这样就可以保证是区间最小值了呢？

dp\[l\]\[k\]维护的是区间 \[l, l + 2^k - 1\] , dp\[r - (1 << k) + 1\]\[k\]维护的是区间 \[r - 2^k + 1, r\] 。

那么只要我们保证![r-2^k+1][r-2_k_1] ≤ ![l+2^k-1][l_2_k-1]就能保证RMQ\[l,r\] = min(dp\[l\]\[k\], dp\[r - (1 << k) + 1\]\[k\])；

接下来我们用分析法来证明这个不等式：

我们假设 ![r-2^k+1][r-2_k_1] ≤ ![l+2^k-1][l_2_k-1] 这个等式成立

即有r - l + 2 ≤ ![2\*2^k][2_2_k]

又因为 k = ![log\_2(r-l+1)][log_2_r-l_1]

那么 r - l + 2 ≤ 2 \* (r - l +1)

则 r - l + 2 ≤ 2\*(r - l) + 2

即 r - l ≤ 2\*(r-l)

所以 r - l ≥ 0，即假设成立

我们举个例子， l = 4，r = 6;

假设数组arr为：1，2，6，8，4，3，7

此时 k = ![log\_2(r-l+1)][log_2_r-l_1] = ![log\_23][log_23] = 1

则区间\[4,6\]的最小值 = min（dp\[4\]\[1\],dp\[5\]\[1\]）

dp\[4\]\[1\] = 4，dp\[5\]\[1\] = 3，所以区间\[4,6\]的最小值 = min(dp\[4\]\[1\],dp\[5\]\[1\]) = 3

我们很容易看出来答案是正确的。

由此给出查询部分代码：

int rmq(int l,int r)
    {
        int k=log2(r-l+1);
        return min(dp[l][k],dp[r-(1<<k)+1][k]);
    }

好了，至此RMQ全部介绍完毕。

[20180411183212554]: /images/20220527/9c9329b22733409fb3bed8991e0c54ad.png
[2_j]: https://private.codecogs.com/gif.latex?2%5Ej
[i]: https://private.codecogs.com/gif.latex?i
[i_2_j-1_-1]: https://latex.codecogs.com/gif.latex?i&plus;2%5E%7Bj-1%7D-1
[i_2_j-1]: https://latex.codecogs.com/gif.latex?i&plus;2%5E%7Bj-1%7D
[i_2_j-1 1]: https://private.codecogs.com/gif.latex?i&plus;2%5Ej-1
[2_j-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bj-1%7D
[log_2_r-l_1]: https://private.codecogs.com/gif.latex?log_2%28r-l&plus;1%29
[r-2_k_1]: https://private.codecogs.com/gif.latex?r-2%5Ek&plus;1
[l_2_k-1]: https://private.codecogs.com/gif.latex?l&plus;2%5Ek-1
[2_2_k]: https://private.codecogs.com/gif.latex?2*2%5Ek
[log_23]: https://private.codecogs.com/gif.latex?log_23