问题概述

  RMQ (Range Minimum/Maximum Query),即区间最值查询,是指对于一个长为n的序列A,回答m次询问区间[l,r][l,r]的最大值或最小值。这种问题我们如果暴力枚举,当查询次数较多且范围较大时复杂度是不能被接受的。下面就来介绍一下一种比较高效且容易写的算法:ST表

算法思想及流程

  ST表(Sparse_Table)算法是一种可以求RMQ问题的在线算法。所谓在线算法,是指以较长时间做预处理,再以较少的时间回答每次询问。而ST表则可以用O(NlogN)O(N \log N)的时间预处理,O(1)O(1)时间询问RMQ问题的算法。

预处理

ST表算法的本质是动态规划

以最大值为例,我们可以设F[i][j]F[i][j]表示从第i个数至向右连续数2j2^j个数的范围内的最大值,即区间[i,i+2j1][i,i+2^j-1]中的最大值。   

例如:A数列为:1,6,2,7,4,2,8,3,7

此时,F[1][0]F[1][0]为区间[1,1+201][1,1+2^0-1]的最大值,即为1 同理,F[2][0]=6,F[3][0]=2F[2][0]=6,F[3][0]=2,因此,我们可以很容易地看出F[i][0]=A[i]F[i][0]=A[i]   

至此,动态规划的状态,边界(初始值)都已经有了,接下来就是状态转移方程   

我们可以考虑将F[i][j]F[i][j]平均分成两段,从i至i+2j11i+2^{j-1}-1为一段,i+2j1i+2^{j-1}i+2ji+2^j为一段。

即区间 并且这两个区间的长度都为 ,则 为这两个区间的最大值。

于是我们有   

但在代码实现的时候需要注意,外层循环要枚举j,内层循环则枚举i,因为我们设的状态是从第i位向至后数长度为2j2^j的区间内的最大值,

即先要求出长度为1的,然后推出长度为2的,再由长度为2的推出长度为4的,以此类推。

如果将i放在外层循环,则无法向后推出,显然是错误的   

时间复杂度O(NlogN)O(N \log N)

询问

  对于询问,因为所求为最大/最小值,则我们只要保证两个区间完全将所求区间覆盖,即只要保证不漏,不需要保证不重。    因此,我们需要找到一个最大的k,使得l+2k<=rl+2^k<=r 求k的过程可以while循环来找,也可以使用自带的函数,即

1
k=(int)(log((double)(r-l+1))/log(2.0));

  找到了这个最大的k之后,只需对F[l][k]F[l][k]F[l2k+1][k]F[l-2^k+1][k]取max即可      时间复杂度O(1)O(1)

代码实现

  注:此代码求的是区间最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define begin Begin
#define next Next
using namespace std;
const int maxn=500000+10;
int n,m,s;
int a[maxn],d[maxn][30];
inline void rmq_init(){
for(int i=1;i<=n;i++)d[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;(i+(1<<j)-1)<=n;i++)
d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
inline int rmq(int x,int y){
int k=(int)(log((double)(y-x+1))/log(2.0));
return min(d[x][k],d[y-(1<<k)+1][k]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("RMQ.in","r",stdin);
freopen("RMQ.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
rmq_init();
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
cout<<rmq(x,y)<<" ";
}
cout<<endl;
return 0;
}