稀疏表通过倍增思想预处理静态数组，实现O(1)区间最值查询。预处理STi表示从i开始长度为2^j的区间最值，递推式为STi=min(STi, STi+(1
稀疏表（Sparse Table）是一种用于快速查询静态数组区间最值（RMQ，Range Minimum/Maximum Query）的数据结构。它通过预处理实现 O(1) 的查询时间复杂度，适用于不修改原数组的场景。预处理时间复杂度为 O(n log n)，空间复杂度也为 O(n log n)。
稀疏表的基本思想
稀疏表的核心是倍增思想：对于每个位置 i，预先计算从 i 开始长度为 2^j 的区间的最值。这样任意一个区间 [l, r] 都可以被两个长度为 2^k 的区间覆盖，其中 k = floor(log2(r – l + 1))，这两个区间有重叠也没关系，只要能完全覆盖 [l, r] 即可。
查询时取这两个区间的最值的较小（或较大）值即可，因此可在常数时间内完成。
实现步骤
1. 预处理对数表（可选但推荐）
为了快速得到每个长度对应的 k = floor(log2(len))，我们可以预处理一个 log 数组，避免每次调用 log 函数。
立即学习“C++免费学习笔记（深入）”；
2. 构建稀疏表 ST
设 ST[i][j] 表示从位置 i 开始，长度为 2^j 的区间中的最小值（或最大值）。递推公式为：
ST[i][0] = arr[i] （长度为 1）
ST[i][j] = min(ST[i][j-1], ST[i + (1
3. 查询 [l, r] 区间最小值
计算 k = log2(r – l + 1)
结果为 min(ST[l][k], ST[r – (1
C++ 实现代码
以下是一个完整的 C++ 实现，支持区间最小值查询：
#include #include #include using namespace std;class SparseTable {private: vector<vector> st; // 稀疏表 vector log; // 预处理 log2 数组 int n;public: // 构造函数，输入数组构建稀疏表 SparseTable(vector& arr) { n = arr.size(); log.resize(n + 1); // 预处理 log2 值 for (int i = 2; i <= n; i++) { log[i] = log[i / 2] + 1; } int k = log[n] + 1; // 最大可能的 j st.assign(n, vector(k)); // 初始化长度为 1 的区间 for (int i = 0; i < n; i++) { st[i][0] = arr[i]; } // 倍增构建稀疏表 for (int j = 1; j < k; j++) { for (int i = 0; i + (1 << j) <= n; i++) { st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]); } } } // 查询 [l, r] 区间最小值，闭区间 int query(int l, int r) { int len = r - l + 1; int k = log[len]; return min(st[l][k], st[r - (1 << k) + 1][k]); }};
使用示例
假设我们有一个数组，想多次查询其子区间的最小值：
#include using namespace std;int main() { vector arr = {1, 3, 2, 5, 4, 7, 0, 6}; SparseTable st(arr); cout << st.query(1, 4) << endl; // 输出 2 (min of [3,2,5,4]) cout << st.query(0, 7) << endl; // 输出 0 cout << st.query(3, 5) << endl; // 输出 4 return 0;}
如果需要支持最大值查询，只需将 min 改为 max 即可。
基本上就这些。稀疏表适合静态数据下的高频 RMQ 查询，实现简单且效率极高。注意它不能处理更新操作，如需支持更新，应考虑线段树或树状数组。
以上就是C++如何实现一个稀疏表(Sparse Table)_C++解决RMQ(区间最值查询)问题的O(1)算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486006.html
微信扫一扫 
支付宝扫一扫 
