区间最值查询（Range Minimum/Maximum Query, RMQ）是算法竞赛和工程实践中的高频问题。ST表（Sparse Table，稀疏表）通过倍增预处理，可以在 O(n log n) 的预处理后，以 O(1) 的时间回答任意区间的最值查询。本文用Java完整实现ST表，并对比其与线段树的适用场景。
一、问题定义
给定一个长度为 n 的数组 a[0..n-1]，回答 q 次查询：区间 [l, r] 内的最大值（或最小值）是多少？
约束：n ≤ 10⁵，q ≤ 10⁶，要求单次查询尽可能快。
二、核心思想：倍增预处理
ST表的核心洞察：任何区间 [l, r] 都可以被两个重叠的、长度为2的幂的区间完全覆盖。
例如区间 [3, 10]（长度8）可以被 [3, 6]（长度4）和 [7, 10]（长度4）覆盖，也可以被 [3, 10] 本身（长度8）覆盖。
预处理 dp[k][i] 表示从位置 i 开始、长度为 2ᵏ 的区间的最值：
dp[0][i] = a[i] // 长度为1
dp[k][i] = max(dp[k-1][i], dp[k-1][i + 2^(k-1)]) // 长度为2^k
查询时，设 len = r - l + 1，k = floor(log₂(len))，则：
answer = max(dp[k][l], dp[k][r - 2^k + 1])
两个长度为 2ᵏ 的区间覆盖 [l, r]，允许重叠，因为最值具有重叠不变性。
三、完整Java实现
import java.util.Arrays;
/**
* ST表 (Sparse Table) - 静态区间最值查询
* 预处理: O(n log n)
* 查询: O(1)
* 不支持修改操作
*/
public class SparseTable {
private int n;
private int[][] st; // st[k][i]: 从i开始长度为2^k的区间的最值
private int[] logTable; // logTable[i]: floor(log2(i))
private boolean isMax; // true=最大值, false=最小值
/**
* 构建ST表
* @param arr 原始数组
* @param isMax true表示查询最大值, false表示最小值
*/
public SparseTable(int[] arr, boolean isMax) {
this.n = arr.length;
this.isMax = isMax;
buildLogTable();
buildST(arr);
}
/**
* 预处理log2表，避免查询时重复计算
*/
private void buildLogTable() {
logTable = new int[n + 1];
logTable[1] = 0;
for (int i = 2; i <= n; i++) {
logTable[i] = logTable[i / 2] + 1;
}
}
/**
* 构建ST表的核心逻辑
*/
private void buildST(int[] arr) {
int maxK = logTable[n] + 1;
st = new int[maxK][n];
// 第0层: 长度为1的区间
for (int i = 0; i < n; i++) {
st[0][i] = arr[i];
}
// 第k层: 长度为2^k的区间
for (int k = 1; k < maxK; k++) {
int len = 1 << k; // 2^k
for (int i = 0; i + len <= n; i++) {
int half = 1 << (k - 1); // 2^(k-1)
if (isMax) {
st[k][i] = Math.max(st[k - 1][i], st[k - 1][i + half]);
} else {
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 query(int l, int r) {
if (l < 0 || r >= n || l > r) {
throw new IllegalArgumentException("Invalid range: [" + l + ", " + r + "]");
}
int len = r - l + 1;
int k = logTable[len];
int p = 1 << k; // 2^k
if (isMax) {
return Math.max(st[k][l], st[k][r - p + 1]);
} else {
return Math.min(st[k][l], st[k][r - p + 1]);
}
}
/**
* 同时维护最大值和最小值的高效方案
*/
public static class STDouble {
private int n;
private int[][] stMax;
private int[][] stMin;
private int[] logTable;
public STDouble(int[] arr) {
this.n = arr.length;
buildLogTable();
int maxK = logTable[n] + 1;
stMax = new int[maxK][n];
stMin = new int[maxK][n];
for (int i = 0; i < n; i++) {
stMax[0][i] = arr[i];
stMin[0][i] = arr[i];
}
for (int k = 1; k < maxK; k++) {
int half = 1 << (k - 1);
for (int i = 0; i + (1 << k) <= n; i++) {
stMax[k][i] = Math.max(stMax[k - 1][i], stMax[k - 1][i + half]);
stMin[k][i] = Math.min(stMin[k - 1][i], stMin[k - 1][i + half]);
}
}
}
private void buildLogTable() {
logTable = new int[n + 1];
for (int i = 2; i <= n; i++) {
logTable[i] = logTable[i / 2] + 1;
}
}
public int queryMax(int l, int r) {
int k = logTable[r - l + 1];
int p = 1 << k;
return Math.max(stMax[k][l], stMax[k][r - p + 1]);
}
public int queryMin(int l, int r) {
int k = logTable[r - l + 1];
int p = 1 << k;
return Math.min(stMin[k][l], stMin[k][r - p + 1]);
}
}
public static void main(String[] args) {
int[] arr = {7, 2, 9, 1, 5, 8, 3, 6, 4, 10};
System.out.println("原始数组: " + Arrays.toString(arr));
System.out.println();
// 最大值ST表
SparseTable stMax = new SparseTable(arr, true);
System.out.println("区间最大值查询:");
int[][] maxQueries = {{0, 9}, {2, 5}, {1, 3}, {6, 8}, {0, 0}};
for (int[] q : maxQueries) {
System.out.printf(" [%d, %d] max = %d%n", q[0], q[1], stMax.query(q[0], q[1]));
}
System.out.println();
// 最小值ST表
SparseTable stMin = new SparseTable(arr, false);
System.out.println("区间最小值查询:");
for (int[] q : maxQueries) {
System.out.printf(" [%d, %d] min = %d%n", q[0], q[1], stMin.query(q[0], q[1]));
}
System.out.println();
// 同时维护最大最小值
STDouble stDouble = new STDouble(arr);
System.out.println("同时查询最大最小值:");
for (int[] q : maxQueries) {
System.out.printf(" [%d, %d] max=%d, min=%d%n",
q[0], q[1], stDouble.queryMax(q[0], q[1]), stDouble.queryMin(q[0], q[1]));
}
// 性能测试
System.out.println("\n性能测试: n=100000, q=1000000");
performanceTest();
}
private static void performanceTest() {
int n = 100000;
int q = 1000000;
int[] largeArr = new int[n];
for (int i = 0; i < n; i++) {
largeArr[i] = (int)(Math.random() * 1000000);
}
long start = System.currentTimeMillis();
SparseTable st = new SparseTable(largeArr, true);
long buildTime = System.currentTimeMillis() - start;
start = System.currentTimeMillis();
for (int i = 0; i < q; i++) {
int l = (int)(Math.random() * n);
int r = l + (int)(Math.random() * (n - l));
st.query(l, r);
}
long queryTime = System.currentTimeMillis() - start;
System.out.printf(" 预处理时间: %d ms%n", buildTime);
System.out.printf(" %d次查询时间: %d ms%n", q, queryTime);
System.out.printf(" 单次查询约: %.3f μs%n", queryTime * 1000.0 / q);
}
}
四、ST表的局限性
ST表最大的优点是 O(1) 查询，但它有一个致命限制：无法处理修改操作。因为修改一个元素可能影响 O(log n) 层预处理结果，更新代价过高。
适用场景对比：
| 数据结构 | 预处理 | 查询 | 修改 | 适用场景 |
|---|---|---|---|---|
| ST表 | O(n log n) | O(1) | 不支持 | 静态数组，大量查询 |
| 线段树 | O(n) | O(log n) | O(log n) | 需要动态修改 |
| 树状数组 | O(n log n) | O(log n) | O(log n) | 前缀查询，单点修改 |
五、扩展：支持GCD查询
ST表不仅适用于最值，还适用于任何满足幂等性的运算（即 f(a, a) = a），如GCD。
/**
* ST表扩展 - 区间GCD查询
* GCD满足幂等性: gcd(x, x) = x
*/
public class STGCD {
private int n;
private int[][] st;
private int[] logTable;
public STGCD(int[] arr) {
this.n = arr.length;
buildLogTable();
int maxK = logTable[n] + 1;
st = new int[maxK][n];
for (int i = 0; i < n; i++) {
st[0][i] = Math.abs(arr[i]);
}
for (int k = 1; k < maxK; k++) {
int half = 1 << (k - 1);
for (int i = 0; i + (1 << k) <= n; i++) {
st[k][i] = gcd(st[k - 1][i], st[k - 1][i + half]);
}
}
}
private int gcd(int a, int b) {
while (b != 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
private void buildLogTable() {
logTable = new int[n + 1];
for (int i = 2; i <= n; i++) {
logTable[i] = logTable[i / 2] + 1;
}
}
public int query(int l, int r) {
int k = logTable[r - l + 1];
int p = 1 << k;
return gcd(st[k][l], st[k][r - p + 1]);
}
public static void main(String[] args) {
int[] arr = {12, 18, 24, 9, 15, 30, 6, 21};
STGCD st = new STGCD(arr);
System.out.println("数组: [12, 18, 24, 9, 15, 30, 6, 21]");
System.out.println("区间GCD查询:");
int[][] queries = {{0, 2}, {1, 4}, {3, 6}, {0, 7}};
for (int[] q : queries) {
System.out.printf(" [%d, %d] GCD = %d%n", q[0], q[1], st.query(q[0], q[1]));
}
}
}
六、经典应用：滑动窗口最值
虽然单调队列更适合滑动窗口，但ST表也能处理固定窗口大小的离线查询。
/**
* 使用ST表解决滑动窗口最值问题
* 给定数组和窗口大小k，求每个窗口的最大值
*/
public class SlidingWindowWithST {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) return new int[0];
SparseTable st = new SparseTable(nums, true);
int n = nums.length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
result[i] = st.query(i, i + k - 1);
}
return result;
}
public static void main(String[] args) {
SlidingWindowWithST solver = new SlidingWindowWithST();
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] result = solver.maxSlidingWindow(nums, k);
System.out.println("数组: " + java.util.Arrays.toString(nums));
System.out.println("窗口大小: " + k);
System.out.println("滑动窗口最大值: " + java.util.Arrays.toString(result));
// 期望: [3, 3, 5, 5, 6, 7]
}
}
七、总结
ST表是静态区间查询问题中查询速度最快的数据结构。其设计精髓在于倍增思想：通过预处理所有长度为2的幂的区间答案，使得任意区间的查询都能通过两个预计算结果合并得到。理解ST表的关键是掌握其”允许重叠”的特性——这正是幂等运算赋予它的独特优势。在无需修改的静态场景下，ST表无疑是RMQ问题的最优解。
