1. 简介
稀疏表（Sparse Table）是一种用于高效处理范围查询问题的数据结构，最常见的是范围最小值查询（RMQ），可以在 O(1) 时间内回答每次查询。
在本文中，我们将通过构建稀疏表的思路，逐步理解其原理、实现方式以及适用场景，并探讨其优缺点。
2. 问题描述
我们以经典的范围最小值查询（Range Minimum Query, RMQ）为例：
给定一个数组 A = {A₁, A₂, ..., Aₙ}，以及若干形如 (L, R) 的查询请求，要求返回数组 A 中从索引 L 到 R（含）之间的最小值。
即：
RMQ(L, R) = \min(A_L, A_{L+1}, ..., A_R)
3. 暴力解法
3.1. 每次查询遍历区间
最直接的方式是，每次查询都从 L 遍历到 R，找出最小值：
List<Integer> answer = new ArrayList<>();
for (int[] query : queries) {
int L = query[0], R = query[1];
int min = A[L];
for (int i = L + 1; i <= R; i++) {
min = Math.min(min, A[i]);
}
answer.add(min);
}
✅ 优点：空间复杂度为 O(1)
❌ 缺点：每次查询时间 O(n)，总时间复杂度 O(mn)，效率低
3.2. 预处理所有区间最小值（O(1) 查询）
我们可以预处理出所有区间 [L, R] 的最小值，存储在一个二维数组 minTable 中：
int[][] minTable = new int[n][n];
for (int i = 0; i < n; i++) {
minTable[i][i] = A[i];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
minTable[i][j] = Math.min(minTable[i][j - 1], A[j]);
}
}
然后每次查询只需 O(1)：
List<Integer> answer = new ArrayList<>();
for (int[] query : queries) {
int L = query[0], R = query[1];
answer.add(minTable[L][R]);
}
✅ 优点：每次查询 O(1)
❌ 缺点：预处理时间 O(n²)，空间复杂度 O(n²)，不适用于大规模数据
4. 稀疏表解法
稀疏表的核心思想是：只预处理长度为 2^k 的区间最小值，从而在查询时通过组合这些区间快速得到答案。
4.1. 核心思想
- 任意长度的区间
[L, R]都可以拆解为若干个长度为 2^k 的子区间。 - 例如
[2, 12]可以拆成[2, 9]（长度 8）、[10, 11]（长度 2）、[12, 12]（长度 1） - 我们只需预处理所有起点
i和长度2^j的区间最小值即可。
4.2. 稀疏表结构定义
我们定义一个二维数组 sparse[i][j]，表示从索引 i 开始，长度为 2^j 的区间的最小值：
sparse[i][j] = \min(A[i], A[i+1], ..., A[i + 2^j - 1])
递推公式如下：
sparse[i][j] = \min(sparse[i][j-1], sparse[i + 2^{j-1}][j-1])
4.3. 构建稀疏表
int[][] sparse = new int[n][log2(n) + 1];
// 初始化长度为1的区间
for (int i = 0; i < n; i++) {
sparse[i][0] = A[i];
}
// 构建其他长度的区间
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
sparse[i][j] = Math.min(
sparse[i][j - 1],
sparse[i + (1 << (j - 1))][j - 1]
);
}
}
✅ 时间复杂度：O(n log n)
✅ 空间复杂度：O(n log n)
4.4. 使用稀疏表进行 RMQ 查询
对于任意区间 [L, R]，我们找到其长度 len = R - L + 1，并计算最大 k 满足 2^k ≤ len，即 k = log2(len)。
然后我们查询两个长度为 2^k 的区间：
int k = log2(R - L + 1);
int min1 = sparse[L][k];
int min2 = sparse[R - (1 << k) + 1][k];
int result = Math.min(min1, min2);
✅ 查询时间复杂度：O(1)
4.5. 预处理 log2 值（可选优化）
为了加速查询中 log2 的计算，我们可以预先计算所有可能的 log2(i) 值：
int[] logTable = new int[n + 1];
logTable[1] = 0;
for (int i = 2; i <= n; i++) {
logTable[i] = logTable[i / 2] + 1;
}
这样在查询时只需查表即可。
5. 稀疏表的通用性
稀疏表不仅适用于 RMQ，也可以用于其他满足以下两个条件的函数 f：
- 结合性（Associative）：
f(a, b, c) = f(f(a, b), c) = f(a, f(b, c)) - 重叠友好性（Overlap-friendly）：
f(a, b, c) = f(f(a, b), f(b, c))
✅ 常见支持函数：
- 最小值（min）
- 最大值（max）
- 最大公约数（GCD）
❌ 不支持函数：
- 求和（sum）——虽然满足结合性，但不满足重叠友好性，不能用 O(1) 查询
6. 稀疏表的局限性
⚠️ 稀疏表适用于静态数组，一旦数组内容发生改变，就需要重新构建整个稀疏表，代价为 O(n log n)。
因此，稀疏表不适合以下场景：
- 数组频繁更新
- 要求支持动态修改的范围查询（如线段树更适合）
7. 总结
| 特性 | 暴力 | 预处理 | 稀疏表 |
|---|---|---|---|
| 查询时间 | O(n) | O(1) | O(1) |
| 预处理时间 | - | O(n²) | O(n log n) |
| 空间复杂度 | O(1) | O(n²) | O(n log n) |
| 支持更新 | ✅ | ❌ | ❌ |
✅ 稀疏表非常适合用于静态数组的范围最小/最大值、GCD 等查询，查询效率高，适合大规模数据处理。
✅ 若需支持更新或求和操作，可考虑使用线段树或前缀和等结构。