ST算法

发表于 | 分类于

介绍

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

​ ST算法就是倍增的产物，ST算法能在O(nlogN)的预处理后，以O(1)的时间求出区间最值问题(当然也能求出其他问题)。思想上类似于动态规划，每次从上一次转移(状态转移方程看下面)。

思路

​ 数列A是一个二维数组，A[i] [j]表示从第i个数字起长度为2的j次方的最大值。每次都成倍增长，公式

长度为2的j次方的最大值是左右俩半长度为2的j-1次方的子区间中较大的一个。

代码

预处理函数

1
2
3
4
5
6
7
8
9
void ST(){
    for(int i=1;i<=n;i++) f[i][0]=a[i];
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}

查询函数

1
2
3
4
int ST_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

例题

P3865 【模板】ST表

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,m;
int f[maxn][50];
int a[maxn];
void ST(){
    for(int i=1;i<=n;i++) f[i][0]=a[i];
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
int ST_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ST();
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        cout<<ST_query(l,r)<<"\n";
    }
    system("pause");
}