ST 表（Sparse Table，稀疏表）初步
定义
ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。其主要用于 RMQ\(^{*}\) 问题。
\(^{*}\)：RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。
思路
设 \(st_{l,x}\) 为区间 \([l, l + 2^x - i]\) 中的最大值。
即有 \(st{l,0} = a_l\)。
其余 \(st{i,j} = \max(st_{i,j−1}, st{i+2^{j-1},j−1})\)。
实现
#include <bits/stdc++.h>
using namespace std;
int n, m, st[100005][25];
inline int read(){ // 快读
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
inline void write(int x){ // 快写
if(x > 9) write(x / 10);
putchar(x % 10 + 48);
}
inline int pow2(int x){//2^x
return 1 << x;
}
int main(){
n = read();
m = read();
for(int i = 1; i <= n; i++) st[i][0] = read();
for(int i = 1; pow2(i) <= n; i++){
for(int l = 1; l <= n; l++){
int r = l + pow2(i) - 1;
if(r <= n)
st[l][i] = max(st[l][i - 1], st[l + pow2(i - 1)][i - 1]);
}
}
while(m--){
int l = read(), r = read();
int k = log2(r - l + 1);
write(max(st[l][k], st[r - pow2(k) + 1][k]));//O(1) 查询
putchar('\n');
}
return 0;
}
优劣
像所有的数据结构一样，ST 表亦有它的优与缺。
优势
-
除 RMQ 以外，还有其它的可重复贡献问题。如区间按位和、区间最大公因数等均可用 ST 表实现维护。
-
时间复杂度较低，码量相对于其他算法较小。查询的时间复杂度可至 \(O(1)\)。
劣势
- 不支持区间修改，也无法很好地应用于其他问题。
Thank's for your reading!