区间最值查询与稀疏表(RMQ with ST)

难度系数:6
适用范围:提高级

区间最值查询(RMQ: range Minimum/Maximum query)
有下列n个元素的数组arr={3,7,1 ,6,8 ,2 ,0,4,9,5},想计算m次任意区间的最大值

方法一:暴力枚举算法


对于每个查询区间进行搜索查询,算法复杂度O(nm),n为元素个数,m为查询次数。当m特别大的时候,此方法表现比较差。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**************************************************************** 
 * Description: C++ implementation of RMQ by emuerations
 * Author: Alex Li
 * Date: 2023-06-13 15:33:36
 * LastEditTime: 2023-06-13 15:42:13
****************************************************************/
#include <iostream>
#include <limits>
using namespace std;

int main(){
    int arr[]={4,9,0,1,2,5,6,3,8,7};
    int answer,left,right;
    while(cin>>left>>right) {
        answer=INT_MIN;  //initialize answer every query
        for (int i =left; i<=right; i++)answer=max(answer,arr[i]);
            cout<<answer<<endl;
    }
}


方法二:打表法


事先将answer[i][j]做好,查询时直接调用。算法复杂度O(n2+m)

answer[i][i]=arr[i];
answer[i][j]=max(answer[i][j-1],arr[j])

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**************************************************************** 
 * Description: C++ implementation of sparse table
 * Author: Alex Li
 * Date: 2023-06-12 19:05:32
 * LastEditTime: 2023-06-12 19:59:53
****************************************************************/
#include <iostream>
using namespace std;

int main(){
    int   arr[]={3,7,9,6,8,2,0,4,1,5};
    int ans[10][10];
    for (int i = 0; i <10; i++){
        for (int j = i; j <10;j++){
            if(i==j)ans[i][j]=arr[i];
            else ans[i][j]=max(ans[i][j-1],arr[j]);
        }
    }
    int left,right;
    while(cin>>left>>right){
        cout<<ans[left][right]<<endl;
    }
    return 0;
}


方法三:利用倍增构建ST表

任意整数均可表示为若干个2的次幂项之和。例如10进制的任何整数,都可以转化成2进制形式。

ST(Sparse Table,稀疏表)算法采用了倍增思想,在O (n logn)时间构造一个二维表之后,可以在O (1)时间在线查询[l , r ]区间的最值,有效解决在线RMQ(Range Minimum/Maximum Query,区间最值查询)问题。

ST表实现: 设 F[i][j] ,它表示[i, i+2j-1]区间的最值,区间长度为2j

根据 倍增思想,长度为2j的区间可被分成两个长度为2j-1的子区间,然后求两个子区间的最值即可。
递推公式:F[i][j]=max(F[i][j-1], F[i+2j-1][j-1])

ST表的建立

若数组长度为n,最大区间长度2k<=n<2k+1
比如,n=8时,k=3。 n=13时,k=3。

以数组arr={3,7,1 ,6,8 ,2 ,0,4,5,9}为例,创建查询最大值的ST表

F[i][j]表示[i, i+2j-1]区间的最值,区间长度为2j

ST表查询

若查询[l, r]区间的最值,则首先计算k值,和前面的计算方法相同,区间长度为r-l+1, 2k<=r-l+1<2k+1,因此k=log2(r-l+1)

若查询区间的长度大于或等于2K且小于2k+1,则根据倍增思想,可以将查询区间分为两个查询区间,取两个区间的最值即可。
两个区间分别为从l向后的2k个数,及r向前的2k个数。这两个区间可能重叠,但对求结果没有影响。

ST预处理的时间为O(nlogn),查询时间为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
/**************************************************************** 
 * Description: C++ implementation of RMQ by ST
 * Author: Alex Li
 * Date: 2023-06-13 19:20:56
 * LastEditTime: 2023-06-13 19:37:51
****************************************************************/

#include <iostream>
#include<cmath>
using namespace std;
int F[10][4];

void createST(int *a,int n){
    for(int i=0;i<n;i++)F[i][0]=a[i];
    int k=log2(n);
    for(int j=1;j<=k;j++){
        for(int i=0;i<=n-(1<<j);i++)
            F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]);
    }
}

int queryST(int l,int r){
    int k=log2(r-l+1);
    return max(F[l][k],F[r-(1<<k)+1][k]);
}

int main(){
    int arr[10]={3,7,1,6,8,2,0,4,5,9};
    createST(arr,10);
    int l,r;
    cin>>l>>r;
    cout<<queryST(l,r);
}

Scroll to Top