C++

「RMQ」区间最值问题详解

区间最值问题是用来解决问一个固定区间内多次询问某个子区间最值的快速算法。

那么我们先来说一下RMQ问题的比较快的算法——

ST(Sparse Table)算法是一个非常有名的在线处理RMQ问题的算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。

首先是预处理,用动态规划(DP)解决。设A[i]是要求区间最值的数列,F[i, j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7,F[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。 F[1,2]=5,F[1,3]=8,F[2,0]=2,F[2,1]=4……从这里可以看出F[i,0]其实就等于A[i]。这样,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])。

然后是查询。取k=[log2(j-i+1)],则有:RMQ(A, i, j)=min{F[i,k],F[j-2^k+1,k]}。 举例说明,要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间的最大值我们可以直接由f[2,2]和f[5,2]得到。

​ [转载自董的博客]

我的感受是:

这是一个神奇的dp,我们上一张图来好好看看这个算法:

如图中的区间增2^n代表从当前n开始(n代表原始序列编号,比如图中的原始序列的7编号为3) n~(n+2^n)的区间内最值,换句话说 dp[i][j]维护的就是序号为i~i+2^j区间的最值

换成普适的公式解释就是

for i : 1 to log(n)/log(2)

  for j : 1 to (n+1-2^i)

     max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]

我们把表记作dp[i][j]来看:如下图的解释,这样就很清楚了!

上一段完整的代码:

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
#define N 105
int dp[N][N],k;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>dp[i][0];
        k=log(double(n))/log(2.0);
    }
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n-(1<<j)+1;i++)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    int m,x,y;
    cin>>m;
    while(m--){
        cin>>x>>y;
        if(x>y) swap(x,y);
        k=log((double)(y-x+1))/log(2.0);
        cout<<min(dp[x][k],dp[y-(1<<k)+1][k])<<endl;
    }
    //debug
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){
    //         cout<<dp[j][i]<<" ";
    //     }
    //     cout<<endl;
    // }
    return 0;
}

/*
/input
8
2 3 7 4 1 5 6 8
/debug 生成的结果
2 3 7 4 1 5 6 8
2 3 4 1 1 5 6 0 
2 1 1 1 1 0 0 0 
1 0 0 0 0 0 0 0 
*/

RMQ问题也可以用线段树或树状数组来维护,由于我的线段树能力很弱,在此不分享了。

分享到