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. 算法实现C3.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(vectorint 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; vectorint 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 表的关键在于理解倍增思想和可重复贡献性质这有助于将其应用到更广泛的问题中。
)
)
