首页 > 代码库 > RMQ算法

RMQ算法

首先是预处理,用动态规划(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 就是这两段(1,4)3,2,4,5 和 (5, 8)6,8,1,2这两段。F[i,j]就是这两段各自最大值中的最大值。于是我们得到了状态转移方程F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])。

/*

*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int maxdp[1000005][20];
int mindp[1000005][20];
int n;
void RMQ() {
    for(int j = 1; 1<<j <= n ; j++){
      for(int i = 1; i+(1<<j)-1 <= n; i++){
        maxdp[i][j] = max(maxdp[i][j-1],maxdp[i+(1<<j-1)][j-1]); 
        mindp[i][j] = min(mindp[i][j-1],mindp[i+(1<<j-1)][j-1]);      
      }    
    }
}
int main() {
    scanf("%d",&n);//输入数据总数
    int a, b, k;
    for(int i = 1; i <= n; i++)
      scanf("%d",&maxdp[i][0]);//数据输入加初始化,即从i开始向右走2的0次方的区间中的最大值,(注//意i到i的长度为一)。
    for (int i  =1; i <= n; i++)
      mindp[i][0]=maxdp[i][0];
    RMQ();
    scanf("%d",&k);
    for(int i = 1; i <= k; i++) {
      scanf("%d%d",&a,&b);
      int x, y, z;
      z=(log(b-a+1)/log(2));
      x=min(mindp[a][z], mindp[b-(1<<z)+1][z]);
      y=max(maxdp[a][z], maxdp[b-(1<<z)+1][z]);
      printf("%d %d\n",x, y);
    }
    return 0;
  }

 

RMQ算法