421 字
1 分钟
ST 表（Sparse Table）
ST 表（Sparse Table）
用于可重复贡献问题的 RMQ，预处理 ，查询 。
核心思想：倍增 + 重叠区间合并
长度为 的区间最值，可由两个长度为 的子区间 合并得到：
关键性质
- 区间可以重叠，不影响结果（因为是 max/min，不是求和）
- 任意区间 可拆成两个长度为 的区间覆盖（）
构建过程
// stmax[start][k]：从 start 开始、长度 2^k 的区间最大值
// 1) 初始化：长度 1for (int i = 1; i <= n; i++) stmax[i][0] = a[i];
// 2) 倍增递推for (int j = 1; j <= __lg(n); j++){ int half = 1 << (j - 1); // 子区间长度 for (int i = 1; i + (1 << j) - 1 <= n; i++) { stmax[i][j] = max(stmax[i][j - 1], stmax[i + half][j - 1]); }}查询过程
int query(int l, int r){ int k = __lg(r - l + 1); // 区间长度的对数 return max(stmax[l][k], stmax[r - (1 << k) + 1][k]); // ← +1 别忘了！}右区间起点要点：r - (1 << k) + 1
| 写法 | 结果 |
|---|---|
r - (1<<k) + 1 | ✅ 正确 |
r - (1<<k) | ❌ 漏掉位置 r |
b - (1 << (__lg(len) + 1)) | ❌ 优先级错，变成 1 << (k+1) |
复杂度陷阱
错误的构建方式—对每个长度独立扫描整个区间，不复用小结果：
// ❌ O(n²) 写法for (int k = 1; k <= __lg(n); k++){ int len = 1 << k; for (int i = 1; i + len - 1 <= n; i++) { int mx = a[i]; for (int j = 1; j < len; j++) // 扫描整个区间！ mx = max(mx, a[i + j]); st[k][i] = mx; }}总操作数 。
始终利用 DP 的 O(1) 合并，不要独立求解每个区间。
计算 的方法对比
| 方法 | 耗时 | 备注 |
|---|---|---|
__lg(x) | 极小（1~3 条指令） | GCC/Clang 内建，映射到 BSR/LZCNT，推荐 |
31 - __builtin_clz(x) | 同上 | 等价实现 |
预处理数组 lg[x] | O(1) 内存访问 | 可移植，标准 C++ |
std::log2(x) | 慢（浮点运算） | 有精度风险，不推荐 |
预处理对数数组的原理
int lg[MAXN];lg[1] = 0;for (int i = 2; i < MAXN; i++) lg[i] = lg[i / 2] + 1;利用递推 在整数上成立，完全避开浮点运算。
完整模板
#include <bits/stdc++.h>using namespace std;
const int MAXN = 50005;int stmax[MAXN][20];int n, q;
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q; for (int i = 1; i <= n; i++) { int x; cin >> x; stmax[i][0] = x; }
int LOG = __lg(n); for (int j = 1; j <= LOG; j++) { int half = 1 << (j - 1); for (int i = 1; i + (1 << j) - 1 <= n; i++) { stmax[i][j] = max(stmax[i][j - 1], stmax[i + half][j - 1]); } }
while (q--) { int l, r; cin >> l >> r; int k = __lg(r - l + 1); int ans = max(stmax[l][k], stmax[r - (1 << k) + 1][k]); cout << ans << "\n"; }
return 0;}踩坑记录
- ==查询公式一定要
r - (1<<k) + 1，少一个+1就漏掉位置 r== - ==
1 << k + 1不是(1<<k) + 1，而是1 << (k+1)，运算符优先级坑== - ==构建时第一维是位置、第二维是幂次，全程保持一致不乱==
- ==
__lg(n)作为幂次上限，不是固定写死 19== - ==每次递归调两次
po()会导致指数级重复计算→快速幂里也犯过这毛病==
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
ST 表（Sparse Table）
https://caoyue.xin/posts/sparse-table/ 部分信息可能已经过时
相关文章 智能推荐