Si_Yue小屋
0%

ST表

发表于 分类于

ST表（Sparse Table），直译为稀疏表，是通过倍增实现的不可修改的区间查询可重复贡献问题的一种数据结构。

可重复贡献问题指的是例如求区间最大值和区间gcd这种合并时区间重叠不影响答案的问题。

代码如下

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e6+5;
const int LOGN=21;
int f[MAXN][LOGN],_log_2[MAXN],n,m;

inline int read(){
    int ret=0,sign=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()){
        if(ch=='-'){
            sign=-sign;
        }
    }
    for(;isdigit(ch);ch=getchar()){
        ret=(ret<<1)+(ret<<3)+ch-'0';
    }
    return ret*sign;
}

void pre(){
    //预处理对数取整
    _log_2[1]=0;
    _log_2[2]=1;
    for(int i=3;i<MAXN;++i){
        _log_2[i]=_log_2[i/2]+1;
    }
}

void _pre(){
    //倍增预处理ST表，第二维代表的是往后跳2^k-1
    //也就是说f[i][k]代表的是在闭区间[i,i+2^k-1]的最大值
    for(int k=1;k<=LOGN;++k){
        for(int i=1;i+(1<<k)-1<=n;++i){
            f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
        }
    }
}

int getmax(int l,int r){
    int ret;
    int s=_log_2[r-l+1];
    //答案就是[l,l+2^s-1]的最大值和[r-2^s+1,r]的最大值中更大的那个
    ret=max(f[l][s],f[r-(1<<s)+1][s]);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    // n=read(),m=read();
    for(int i=1;i<=n;++i)cin>>f[i][0];
    // for(int i=1;i<=n;++i)f[i][0]=read();
    pre();
    _pre();
    for(int i=1;i<=m;++i){
        int l,r;cin>>l>>r;
        // int l,r;l=read(),r=read();
        cout<<getmax(l,r)<<'\n';
        // printf("%d\n",getmax(l,r));
    }
    return 0;
}

ST 表能较好的维护「可重复贡献」的区间信息（同时也应满足结合律），时间复杂度较低，代码量相对其他算法很小。但是，ST 表能维护的信息非常有限，不能较好地扩展，并且不支持修改操作。