稀疏表通过倍增思想预处理静态数组，实现O(1)区间最值查询。预处理STi表示从i开始长度为2^j的区间最值，递推式为STi=min(STi, STi+(1<<j-1))，查询时取覆盖[l,r]的两个2^k长度区间的最值，k=floor(log2(r-l+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 <vector>
#include <cmath>
#include <algorithm>
using namespace std;
class SparseTable {
private:
vector<vector<int>> st; // 稀疏表
vector<int> log; // 预处理 log2 数组
int n;
public:
// 构造函数，输入数组构建稀疏表
SparseTable(vector<int>& 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<int>(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 <iostream>
using namespace std;
int main() {
vector<int> 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 查询，实现简单且效率极高。注意它不能处理更新操作，如需支持更新，应考虑线段树或树状数组。
