什么是 ST 表
ST 表（Sparse Table，稀疏表）用于解决可重复贡献问题的区间查询：预处理 O(n log n)，单次查询 O(1)，是处理”大量询问、无修改”场景的最快数据结构。它的前提是运算 opt 满足结合律且可重复贡献（x opt x = x），例如：
- 区间最大值：max(x, x) = x ✅
- 区间 GCD：gcd(x, x) = x ✅
- 区间按位与/或：同样可重复贡献 ✅
- 区间和：1+1 ≠ 1 ❌ —— 求区间和时预处理的区间若重叠会把重叠部分算两次，所以 ST 表不能用于区间和。
倍增思想
定义 f[i][j] 表示从 i 开始、长度为 2^j 的区间 [i, i+2^j-1] 的答案。显然 f[i][0] = a[i]，转移：
f[i][j] = opt(f[i][j-1], f[i + 2^(j-1)][j-1])
即把长度为 2^j 的区间拆成两个相邻的 2^(j-1) 区间合并。
为什么查询是 O(1)
查询 [l, r] 时，取 k = ⌊log2(r-l+1)⌋，用两个可能重叠但完全覆盖的预处理区间求答案：
answer = opt(f[l][k], f[r - 2^k + 1][k])
由于运算是”可重复贡献”的，重叠无影响，而两个区间合起来恰好覆盖 [l, r]，所以答案正确——这就是 ST 表能做到 O(1) 查询的关键。
C++ 实现（区间最大值）
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int st[MAXN][20]; // 20 ≈ log2(1e5)
int lg2[MAXN];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &st[i][0]);
// 预处理 log2（整数向下取整）
for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
// 预处理 st 表
for (int j = 1; j <= lg2[n]; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
int k = lg2[r - l + 1];
printf("%dn", max(st[l][k], st[r - (1 << k) + 1][k]));
}
return 0;
}
复杂度与局限
| 项 | ST 表 | 线段树 |
|---|---|---|
| 预处理 | O(n log n) | O(n) |
| 单次查询 | O(1) | O(log n) |
| 支持修改 | ❌ 不支持 | ✅ 支持 |
| 适用运算 | 可重复贡献 | 任意结合律运算（含区间和） |
选型建议：查询极多、无修改、运算是 max/gcd/位运算 → ST 表（O(1) 查询吊打线段树）；需要单点/区间修改 → 线段树；区间和类问题 → 只能线段树/树状数组。