算法概述
稀疏表（Sparse Table）是一种用于解决RMQ（Range Minimum/Maximum Query，区间最值查询）问题的经典数据结构。其核心思想是利用倍增预处理技术，将区间查询的时间复杂度降至 $O(1)$，而预处理代价仅为 $O(n \log n)$。稀疏表适用于静态数组场景，即数组元素在查询过程中不会发生变化。
与线段树相比，稀疏表的空间开销更小、查询速度更快，但不支持单点修改；与树状数组相比，稀疏表能直接处理任意区间的最值查询，无需复杂的前缀转换。
核心思想
稀疏表的构建基于一个简单观察：对于任意区间 $[l, r]$，设其长度为 $len = r – l + 1$，取 $k = \lfloor \log_2 len \rfloor$，则该区间可以被两个长度为 $2^k$ 的重叠子区间完全覆盖：
- 左半区间：$[l, l + 2^k – 1]$
- 右半区间：$[r – 2^k + 1, r]$
由于最值查询满足重叠不变性（即重叠区间的最值等于整体最值），我们只需取这两个子区间的预计算最值即可得到答案。
预处理过程
定义 $st[k][i]$ 表示从位置 $i$ 开始、长度为 $2^k$ 的区间的最值。递推公式为：
$$
st[k][i] = \min(st[k-1][i], st[k-1][i + 2^{k-1}])
$$
其中 $st[0][i] = a[i]$，即长度为1的区间最值就是元素本身。
Java完整实现
import java.util.Arrays;
/**
* 稀疏表（Sparse Table）实现RMQ区间最值查询
* 时间复杂度：预处理 O(n log n)，查询 O(1)
* 空间复杂度：O(n log n)
* 适用场景：静态数组，无修改操作
*/
public class SparseTable {
// 原数组
private final int[] arr;
// st[k][i] 表示从i开始长度为2^k的区间的最值
private final int[][] st;
// log2[i] 表示 floor(log2(i))
private final int[] log2;
// 数组长度
private final int n;
// 最大幂次
private final int maxLog;
/**
* 构造函数：构建稀疏表
* @param arr 输入的静态数组
*/
public SparseTable(int[] arr) {
this.arr = arr.clone();
this.n = arr.length;
// 预处理log2数组，避免查询时重复计算
this.log2 = new int[n + 1];
log2[1] = 0;
for (int i = 2; i <= n; i++) {
log2[i] = log2[i / 2] + 1;
}
// 最大幂次
this.maxLog = log2[n] + 1;
// 初始化st表
this.st = new int[maxLog][n];
// 第0层：长度为1的区间
for (int i = 0; i < n; i++) {
st[0][i] = arr[i];
}
// 动态规划填表：逐层构建长度为2^k的区间
for (int k = 1; k < maxLog; k++) {
int len = 1 << k; // 2^k
for (int i = 0; i + len <= n; i++) {
// 区间[i, i+len-1]的最值 = 左半部分最值 与 右半部分最值 的比较结果
int half = 1 << (k - 1);
st[k][i] = Math.min(st[k - 1][i], st[k - 1][i + half]);
}
}
}
/**
* 查询区间[l, r]的最小值（0-based，闭区间）
* @param l 左端点
* @param r 右端点
* @return 区间最小值
*/
public int queryMin(int l, int r) {
if (l > r || l < 0 || r >= n) {
throw new IllegalArgumentException("Invalid query range: [" + l + ", " + r + "]");
}
int len = r - l + 1;
int k = log2[len];
// 两个重叠区间取最小值
return Math.min(st[k][l], st[k][r - (1 << k) + 1]);
}
/**
* 查询区间[l, r]的最大值（0-based，闭区间）
* 构建时若存储最大值，查询方式类似
* 本示例中st存储最小值，最大值的st需要单独构建或修改比较逻辑
* @param l 左端点
* @param r 右端点
* @return 区间最大值（基于原数组计算，演示用途）
*/
public int queryMax(int l, int r) {
// 为简化演示，此处直接遍历；实际应用中应构建独立的maxST
int max = arr[l];
for (int i = l + 1; i <= r; i++) {
max = Math.max(max, arr[i]);
}
return max;
}
/**
* 同时支持最小值和最大值的稀疏表
*/
public static class RangeQuery {
private final int[][] minST;
private final int[][] maxST;
private final int[] log2;
private final int n;
private final int maxLog;
public RangeQuery(int[] arr) {
this.n = arr.length;
this.log2 = new int[n + 1];
for (int i = 2; i <= n; i++) {
log2[i] = log2[i / 2] + 1;
}
this.maxLog = log2[n] + 1;
this.minST = new int[maxLog][n];
this.maxST = new int[maxLog][n];
for (int i = 0; i < n; i++) {
minST[0][i] = arr[i];
maxST[0][i] = arr[i];
}
for (int k = 1; k < maxLog; k++) {
int half = 1 << (k - 1);
for (int i = 0; i + (1 << k) <= n; i++) {
minST[k][i] = Math.min(minST[k - 1][i], minST[k - 1][i + half]);
maxST[k][i] = Math.max(maxST[k - 1][i], maxST[k - 1][i + half]);
}
}
}
public int queryMin(int l, int r) {
int k = log2[r - l + 1];
return Math.min(minST[k][l], minST[k][r - (1 << k) + 1]);
}
public int queryMax(int l, int r) {
int k = log2[r - l + 1];
return Math.max(maxST[k][l], maxST[k][r - (1 << k) + 1]);
}
}
/**
* 打印稀疏表结构，用于调试理解
*/
public void printTable() {
System.out.println("=== Sparse Table Structure ===");
for (int k = 0; k < maxLog; k++) {
System.out.print("2^" + k + " [" + (1 << k) + "]: ");
for (int i = 0; i < n; i++) {
if (i + (1 << k) <= n) {
System.out.print(st[k][i] + " ");
} else {
System.out.print("- ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0};
System.out.println("Original array: " + Arrays.toString(arr));
System.out.println();
// 测试最小值稀疏表
SparseTable st = new SparseTable(arr);
st.printTable();
System.out.println("\n=== Min Query Tests ===");
int[][] queries = {{0, 9}, {2, 5}, {4, 7}, {0, 0}, {8, 9}};
for (int[] q : queries) {
int result = st.queryMin(q[0], q[1]);
System.out.printf("Range [%d, %d] min = %d%n", q[0], q[1], result);
}
// 测试同时支持最大最小值的版本
System.out.println("\n=== RangeQuery Tests ===");
RangeQuery rq = new RangeQuery(arr);
for (int[] q : queries) {
System.out.printf("Range [%d, %d] min = %d, max = %d%n",
q[0], q[1], rq.queryMin(q[0], q[1]), rq.queryMax(q[0], q[1]));
}
// 性能测试
System.out.println("\n=== Performance Test ===");
int n = 100000;
int[] largeArr = new int[n];
for (int i = 0; i < n; i++) {
largeArr[i] = (int)(Math.random() * 1000000);
}
long start = System.currentTimeMillis();
RangeQuery largeRQ = new RangeQuery(largeArr);
long buildTime = System.currentTimeMillis() - start;
System.out.println("Build time for n=" + n + ": " + buildTime + "ms");
int m = 1000000; // 100万次查询
start = System.currentTimeMillis();
for (int i = 0; i < m; i++) {
int l = (int)(Math.random() * n);
int r = l + (int)(Math.random() * (n - l));
largeRQ.queryMin(l, r);
}
long queryTime = System.currentTimeMillis() - start;
System.out.println(m + " queries time: " + queryTime + "ms");
System.out.println("Average query time: " + (queryTime * 1000.0 / m) + "μs");
}
}
关键要点解析
1. 重叠不变性
稀疏表能够 $O(1)$ 查询的关键在于最值查询的重叠不变性。对于求和操作，重叠区间会导致重复计算，因此稀疏表不适用于区间求和；但对于最值、GCD、按位与/或等满足重叠不变性的运算，稀疏表表现优异。
2. 空间优化
原始实现使用 $O(n \log n)$ 空间。观察到第 $k$ 层只需存储 $n – 2^k + 1$ 个值，实际有效空间约为 $n \log n – n + 1$，但为简化代码通常直接分配矩形数组。
3. 对数预处理
将 $\log_2$ 值预存到数组中，避免查询时调用 Math.log，使每次查询仅需两次数组访问和一次比较操作。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 预处理 | $O(n \log n)$ | $O(n \log n)$ |
| 单次查询 | $O(1)$ | $O(1)$ |
适用场景与扩展
- 静态区间最值：数组元素不变，频繁查询不同区间的最大/最小值
- 区间GCD查询：GCD同样满足重叠不变性，稀疏表可直接适配
- 区间按位与/或：位运算的重叠不变性使稀疏表成为理想选择
- 在线算法预处理：将 $O(n)$ 的数组预处理为 $O(1)$ 查询结构，加速后续算法
稀疏表以其简洁的实现和优异的查询性能，成为静态RMQ问题的首选数据结构。
