参考博客

简介

RMQ问题是指对于长度为 n 的数列 A ，回答若干询问 RMQ(A,i,j)(i,j≤n) ，返回数列 A 中下标在 i , j 里的最小（大）值，也就是说RMQ问题是指求区间最值的问题。

解法：线段树， ST 等等

注意：ST算法只适用于静态区间求最值，如果是动态的只能乖乖的打线段树

基本思想

ST算法它的本质相当于是动态规划，下面我们以求最大值为例（最小值求法和最大值差不多）

我们用 f[i][j] 表示以 i 为起点，连续 2^j 个数中的最大值，例如 f[2][2] 就表示第 2 个数到第 5 个数的最大值

ST预处理

我们用 A 表示原序列，由于 20=1 ，按照 f 数组的定义，f[i][0] 就等于 A[i]（初始化）

对于其他的处理，我们看下图：

对于每一个 f 数组表示的序列，我们都把它拆成两部分，很明显它的最大值就是这两部分的最大值中较大的那一个。那么转移方程就是：f[i][j]=max(f[i][j-1],f[i+(1<<(j-1)][j-1]) （ 1<<j 是位运算，相当于 2^j ）

1
2
3
4
5
6
7
8
9
void ST(){//区间最值查询预处理
    for(int i=1;i<=n;i++)
    f[i][0]=a[i];

    for(int j=1;(1<<(j-1))<=n;j++)//枚举某段区间的长度拆成两半
        for(int i=1;i+(1<<(j-1))<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            //f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

RMQ查询

假设要查询的区间为 [l,r] ，我们用 L 表示区间 [l,r] 的长度，即 L=r-l+1 ，下面用 k 表示 log(L)

其中查询的话，区间长度 L 不一定刚好是 2 的多少次方，又因为 log(L) 是向下取整，那么 2^k 就有可能小于 L ，这样的话，我们就不能直接用 f[l][k] 来表示答案，不然的话会有遗漏（例如上图中的左半部分）

正确的做法是我们就从 l 往右取 2^k 个（即 f[l][k] ），从 r 往左取 2^k 个（即 f[r-(1<<k)+1][k] ），这样就能保证区间 [l,r] 都被访问到了，重复计算的不用担心这是计算最值而不是求和

所以答案就是 ans=max{f[l][k],f[r-(1<<k)+1][k]}

1
2
3
4
5
6
7
8
9
//O(1)的RMQ询问
for(int i=1;i<=m;i++){
    cin>>l>>r;
    int k=Log[r-l+1];
    ans=max(f[l][k],f[r-(1<<k)+1][k]);
    //ans=min(f[l][k],f[r-(1<<k)+1][k])
    printf("%d\n",ans);
    //cout<<ans<<endl;
}

Log 数组需要预处理出来，下面就讲

预处理 Log 数组

  • Log 数组是向下取整的
  • Log[i]=Log[i/2]+1
1
2
3
4
5
void GetLog(){//预处理获得向下取整的Log数
    Log[1]=0;
    for(int i=2;i<=n+1;i++)
    Log[i]=Log[i/2]+1;
}

复杂度分析

其实时间复杂度看代码很容易可以分析出来：

  • 预处理部分：j 循环是O(logn)，i 循环是 O(n) ，总共是 O(nlogn)

  • 查询部分：查询的问题相当于已经打表出来了所以就是 O(1)

例题

模板题：给定一个长度为N的数列，M次询问，求出每一次询问的区间内数字的最大值，请注意最大数据时限只有 0.8s ，数据强度不低，请务必保证你的每次查询复杂度为 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;//最大单元数
const int M=25;//2^i中i的最大值也就是某段区间的最大长度
const int inf=0x3f3f3f3f;

int n,m;//单元数和查询数
int a[N],Log[N];
int f[N][M];//存储以i为起点长为2^j的区间内最值

void GetLog(){//预处理获得向下取整的Log数
    Log[1]=0;
    for(int i=2;i<=n+1;i++)
    Log[i]=Log[i/2]+1;
}

void ST(){//区间最值查询预处理
    for(int i=1;i<=n;i++)
    f[i][0]=a[i];

    for(int j=1;(1<<(j-1))<=n;j++)//枚举某段区间的长度拆成两半
        for(int i=1;i+(1<<(j-1))<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            //f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n>>m){
        GetLog();
        for(int i=1;i<=n;i++)
        cin>>a[i];
        ST();

        int l,r,ans=-1;//ans=inf

        //O(1)的RMQ询问
        for(int i=1;i<=m;i++){
            cin>>l>>r;
            int k=Log[r-l+1];
            ans=max(f[l][k],f[r-(1<<k)+1][k]);
            //ans=min(f[l][k],f[r-(1<<k)+1][k])
            printf("%d\n",ans);
            //cout<<ans<<endl;
        }
    }
    return 0;
}