st表（稀疏表）

发表于 分类于 阅读次数： 本文字数： 488 阅读时长 ≈ 2 分钟

原题与参考：
https://www.luogu.com.cn/problem/P3865
https://oi-wiki.org/ds/sparse-table/

模板题题意

给定个数，有个询问，对于每个询问，你需要回答区间中的最大值

简介

ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。

可重复贡献问题：对于运算opt，满足，如和。

比起线段树，只能静态查询，不能修改信息。
使用倍增思想，时间复杂度：

步骤

对数初处理

1
2
3
4
int lg[N];//对数表
for(int i=2;i<=n;i++){//初始化对数表
    lg[i]=lg[i>>1]+1;
}

转移方程

设为数序列，为区间的最大值，则

这里有张动图来着

1
2
3
4
5
6
7
int w=1;
for(int j=1;j<=lg[n];j++){
    for(int i=1;i<=n-w;i++){
        f[i][j]=max(f[i][j-1],f[i+w][j-1]);
    }
    w<<=1;
}

询问

询问时，把区间分成和，其中
即查询
这里有张动图来着

1
2
3
scanf("%d%d",&l,&r);
s=lg[r-l+1];
printf("%d\n",max(f[l][s],f[r-(1<<s)+1][s]));

总代码

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
#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
int n,m;//数列的长度,询问的个数
int f[N][22];//区间[i,i+2^j-1]的最大值
int lg[N];//对数表
int main() {
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++){//初始化对数表
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&f[i][0]);
    }
    int w=1;
    for(int j=1;j<=lg[n];j++){
        for(int i=1;i<=n-w;i++){
            f[i][j]=max(f[i][j-1],f[i+w][j-1]);
        }
        w<<=1;
    }
    int l,r,s;
    while(m--){
        scanf("%d%d",&l,&r);
        s=lg[r-l+1];
        printf("%d\n",max(f[l][s],f[r-(1<<s)+1][s]));
    }
    return 0;
}