\(update : 2025/10/28\)
其实我直到现在还不会st表,遂写一份博客来加强记忆
ST表 (\(Sparse\; Table\)), 用于高效查询区间信息 (可重复贡献的信息) 的数据结构
应用范围很广, 多数用于 \(RMQ\)问题
复杂度
时间 : \(O(n\;log n)\) 建表, \(O(1)\) 查询
空间 : \(O(n\;log n)\)
思想(原理)
基于倍增的方法记录每个点开始后 \(2^k\) 的区间信息, 查询时用含交的两段信息的并集计算答案
实现
//May all the beauty be blessed.
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int st[100010][25];
int n,m;signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>st[i][0];for(int i=1;i<=20;i++){if((1<<i)>n) break;for(int j=1;j+(1<<i)-1<=n;j++){ //这里可以联系倍增 st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);}}while(m--){int l,r;cin>>l>>r;int k=__lg(r-l+1);cout<<max(st[l][k],st[r-(1<<k)+1][k])<<'\n'; //含交的两端信息 }
}
/**/例题
P3865 【模板】ST 表 & RMQ 问题