1. 什么是 ST 表
ST 表（Sparse Table，稀疏表）是一种用于解决静态区间最值查询（RMQ）问题的数据结构。它可以在 O(n log n) 的预处理时间后，以 O(1) 的时间复杂度回答任意区间 [l, r] 的最小值、最大值、最大公约数等可重复贡献问题的查询。
2. 核心思想与原理
ST 表的核心思想是倍增和动态规划。对于长度为 n 的数组 arr，我们预处理一个二维数组 st[i][j]，表示从位置 i 开始，长度为 2^j 的区间（即区间 [i, i + 2^j - 1]）的查询结果（如最大值）。
状态转移方程为：
st[i][j] = f(st[i][j-1], st[i + 2^(j-1)][j-1])其中 f 是满足可重复贡献性质的二元运算，如 max、min、gcd 等。
对于查询区间 [l, r]，我们找到最大的 k 使得 2^k ≤ (r - l + 1)，然后通过两个长度为 2^k 的区间覆盖 [l, r]：
ans = f(st[l][k], st[r - 2^k + 1][k])由于运算 f 满足可重复贡献性质，即使这两个区间有重叠，最终结果也是正确的。
3. 算法实现（C++）
3.1 预处理
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int LOG = 20; // log2(MAXN) int st[MAXN][LOG]; int log2_pre[MAXN]; // 预处理 log2 值 void preprocess(vector<int>& arr) { int n = arr.size(); // 预处理 log2 值 log2_pre[1] = 0; for (int i = 2; i <= n; i++) { log2_pre[i] = log2_pre[i / 2] + 1; } // 初始化：长度为 1 的区间 for (int i = 0; i < n; i++) { st[i][0] = arr[i]; } // 动态规划构建 ST 表 for (int j = 1; j < LOG; j++) { for (int i = 0; i + (1 << j) - 1 < n; i++) { st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]); } } }3.2 查询操作
int query(int l, int r) { int k = log2_pre[r - l + 1]; return max(st[l][k], st[r - (1 << k) + 1][k]); }4. 时间复杂度分析
- 预处理：O(n log n)
- 单次查询：O(1)
- 空间复杂度：O(n log n)
与线段树（查询 O(log n)）相比，ST 表在查询速度上更有优势，但不支持修改操作，适用于静态数据场景。
5. 应用场景
- 静态 RMQ 问题：数组固定不变，频繁查询区间最值
- LCA（最近公共祖先）：结合欧拉序和 ST 表可以在 O(1) 时间内回答 LCA 查询
- 区间 GCD 查询：同样满足可重复贡献性质
- 二维 RMQ：扩展到二维数组的静态区间查询
- 竞赛编程：常用于需要快速区间查询的题目
6. 优缺点总结
| 优点 | 缺点 |
|---|---|
| 查询速度极快（O(1)） | 不支持修改操作 |
| 代码实现相对简单 | 空间复杂度较高（O(n log n)） |
| 适用于静态数据场景 | 只能处理可重复贡献问题 |
| 可扩展到多维 | 预处理时间较长 |
7. 实战例题
7.1 洛谷 P3865 【模板】ST 表
题目描述：给定一个长度为 n 的数列，和 m 次询问，每次询问区间 [l, r] 的最大值。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int LOG = 17; int st[MAXN][LOG]; int log2_pre[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } // 预处理 log2 log2_pre[1] = 0; for (int i = 2; i <= n; i++) { log2_pre[i] = log2_pre[i / 2] + 1; } // 构建 ST 表 for (int i = 0; i < n; i++) { st[i][0] = arr[i]; } for (int j = 1; j < LOG; j++) { for (int i = 0; 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; cin >> l >> r; l--; r--; // 转换为 0-based int k = log2_pre[r - l + 1]; cout << max(st[l][k], st[r - (1 << k) + 1][k]) << "\n"; } return 0; }8. 扩展与变种
8.1 支持其他运算
ST 表可以支持任何满足可重复贡献和结合律的运算：
- 最小值：min
- 最大公约数：gcd
- 按位与：&
- 按位或：|
8.2 二维 ST 表
对于二维数组，可以预处理四维数组 st[x][y][kx][ky]，表示以 (x, y) 为左上角，宽度为 2^kx，高度为 2^ky 的矩形区域的查询结果。
9. 总结
ST 表是解决静态区间查询问题的利器，特别适合查询频繁但数据不变的场景。虽然不支持修改，但其 O(1) 的查询复杂度在竞赛和某些工程场景中具有明显优势。掌握 ST 表的关键在于理解倍增思想和可重复贡献性质，这有助于将其应用到更广泛的问题中。