C++ ST表（Sparse Table）详解

快速静态区间查询

1. ST表概念与适用场景

ST表（Sparse Table，稀疏表）是一种用于在静态数组（内容不变）上快速查询区间信息的数据结构。它特别擅长处理那些具有结合律并且结果可以重复计算而不影响最终值的操作（幂等性，如min/max）。

主要适用场景：

  • 区间最值（RMQ - Range Minimum/Maximum Query）
  • 区间最大公约数（GCD）
  • 区间按位与（AND）、按位或（OR）
  • 其他满足结合律且（对于O(1)查询）幂等的操作

示例数组： (这个数组将在下面被用来演示)

核心特点与对比：

数据结构 预处理时间 查询时间 更新时间 空间复杂度 是否支持动态
ST表 O(n log n) O(1)* 不支持 O(n log n) 否 (静态)
线段树 O(n) O(log n) O(log n) O(n) 是 (动态)
树状数组 O(n log n) / O(n) O(log n) O(log n) O(n) 是 (动态)

* O(1) 查询适用于幂等操作（如 min, max, gcd, and, or）。对于非幂等操作（如区间和），ST 表查询需要 O(log n) 或无法直接应用。

2. ST表预处理过程

ST表的核心思想是动态规划：预先计算并存储所有长度为 2 的幂次方的区间的结果。查询时，任何区间都可以被表示为（最多）两个这样的预计算区间的组合。

定义：我们用 st[k][i] 表示原数组中，从索引 i 开始，长度为 2k 的区间 [i, i + 2k - 1] 的计算结果（例如，最小值）。

预处理递推公式 (以求区间最小值为例)

st[k][i] = min(st[k-1][i], st[k-1][i + 2k-1])

  • 基础情况 (k=0): st[0][i] 存储的是长度为 20 = 1 的区间的值，即原数组元素 a[i]。
  • 递推步骤 (k > 0): 一个长度为 2k 的区间 [i, i + 2k - 1] 可以被完美地拆分成两个相邻且等长的子区间：
    • 左半部分：[i, i + 2k-1 - 1] (从 i 开始，长度 2k-1)，其结果为 st[k-1][i]。
    • 右半部分：[i + 2k-1, i + 2k - 1] (从 i + 2k-1 开始，长度 2k-1)，其结果为 st[k-1][i + 2k-1]。
    将这两个子区间的结果合并（这里是取最小值），就得到了当前区间 st[k][i] 的结果。

预处理演示 (区间最小值)

请输入一个小的整数数组（用空格分隔，例如：9 3 7 1 8 12 6 5）：

构建 ST 表 (st[k][i])

3. 区间查询 (以区间最小值为例)

ST表的最大优势在于能够以 O(1) 的时间复杂度查询静态区间信息（对于幂等操作）。这是通过巧妙地选择两个可能重叠的、长度为 2 的幂的预计算区间来实现的。

区间 [L, R] 查询步骤
  1. 计算查询区间的长度：len = R - L + 1
  2. 计算一个关键值 k，使得 2k 是不大于 len 的最大 2 的幂。即 k = ⌊log2(len)⌋。 这保证了我们选取的子区间长度不会超过原区间长度。
  3. 选择两个长度为 2k 的预计算区间，它们的并集完全覆盖查询区间 [L, R]：
    • 第一个区间：从 L 开始，长度为 2k，即 [L, L + 2k - 1]。其结果为 st[k][L]。
    • 第二个区间：结尾在 R，长度为 2k，即 [R - 2k + 1, R]。其结果为 st[k][R - 2k + 1]。

    注意：这两个区间可能会有重叠部分。对于 min, max, gcd, and, or 等幂等操作，重叠部分计算两次不影响最终结果。

  4. 合并这两个子区间的结果，得到最终答案：result = min(st[k][L], st[k][R - 2k + 1])

查询演示

使用上一步构建的ST表 (如果尚未构建，请先返回上一页构建)。请输入查询区间的左右端点 (0-based index)：

4. ST表的局限性与适用性总结

ST表虽然查询效率极高，但它的应用场景有明确的限制。

适用与不适用场景：

适用

区间最小值 (Min)

适用

区间最大值 (Max)

适用

区间最大公约数 (GCD)

适用

区间按位与 (AND)

适用

区间按位或 (OR)

适用

其他结合律 & 幂等操作

不适用

区间和 (Sum)

不适用

区间异或 (XOR)

不适用

需要修改数组元素

不适用

动态增删元素

低效

非幂等结合律操作查询 (需 O(log n))

核心限制总结

  • 静态结构：ST表基于预处理，不支持对原数组进行修改。任何修改都需要 O(n log n) 的时间重建整个表。
  • 操作限制：
    • 必须满足结合律 ( e.g., `f(a, f(b, c)) = f(f(a, b), c)` )。
    • 若要实现 O(1) 查询，操作还需满足幂等性 ( e.g., `f(a, a) = a` )。像 min, max, gcd, and, or 都满足幂等性。区间和、区间异或不满足幂等性，因为重复计算重叠部分会影响结果。
  • 空间复杂度较高：O(n log n) 的空间开销，对于 n 很大的情况可能成为瓶颈。

当需要处理动态修改或不满足幂等性的操作时，应考虑使用线段树或树状数组等其他数据结构。

5.1 知识点测验

5.2 编程练习

练习 1: 区间最小值查询 (RMQ)

给定一个长度为 n 的整数数组 a。你需要实现一个数据结构，支持快速查询任意给定区间 [L, R] (0 ≤ L ≤ R < n) 内的最小值。

要求：

  • 预处理时间复杂度：O(n log n)
  • 单次查询时间复杂度：O(1)
  • 数组大小 n 最大可达 105。
练习 2: 区间最大公约数查询 (GCD)

给定一个长度为 n 的正整数数组 a。你需要实现一个数据结构，支持快速查询任意给定区间 [L, R] 内所有元素的最大公约数 (GCD)。

提示：最大公约数运算 gcd(a, b) 满足结合律 (gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)) 和幂等性 (gcd(a, a) = a)。因此，ST 表非常适合解决此问题。

要求：

  • 预处理时间复杂度：O(n log n)
  • 单次查询时间复杂度：O(1) (假设单次 gcd 计算为 O(1) 或 O(log value))
  • 数组大小 n 最大可达 105。

6. 实现注意事项

内存管理

  • ST表需要 O(n log n) 的存储空间。对于 n=105，log2n ≈ 17，所以大约需要 17 * 105 个整数的存储空间。
  • 选择合适的存储方式：
    • 动态二维数组 (vector): vector> st; 推荐使用，更灵活。需要在构建时 resize。例如: st.resize(K + 1, vector(n)); 其中 K = ⌊log2n⌋。
    • 静态二维数组: int st[MAX_K][MAX_N]; 需要预估 K 和 N 的最大值 (例如 MAX_K = 20, MAX_N = 100005)。注意可能造成内存浪费或不足。
  • 注意栈空间限制，如果 n 很大，避免在函数内部声明大型静态数组。

数据范围与类型

  • 检查输入数组的长度 n 和查询的 L, R 是否在有效范围内 (0 ≤ L ≤ R < n)。
  • 处理边界情况，例如单元素查询 (L == R)。
  • 如果原数组元素或计算结果（如 GCD）可能很大，使用 long long 类型防止整数溢出。

对数计算 (k 的计算)

  • 查询时需要计算 k = ⌊log2(len)⌋。
  • 方法一：预处理对数表 (推荐，最快)： 
    // 预处理 O(N)
int log_table[MAX_N + 1];
void precompute_log(int n) {
    log_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_table[i] = log_table[i / 2] + 1;
    }
}
// 查询时 O(1): k = log_table[R - L + 1];
  • 方法二：使用内置函数 (GCC/Clang): 
    // 查询时 O(1)，但可能有微小常数开销
int k = 31 - __builtin_clz(R - L + 1); // For 32-bit int
// or __builtin_log2(R - L + 1) in C++20 <cmath>
// or log2(R - L + 1) from <cmath> (returns double, need floor)

    __builtin_clz 计算前导零的数量，效率很高。

  • 方法三：直接计算 (较慢): 
    // 查询时 O(log len)
int k = 0;
while ((1 << (k + 1)) <= (R - L + 1)) {
    k++;
}

常见错误

  • 预处理循环边界错误：第二层循环 i 的上界应为 n - (1 << k) 或类似形式，确保 i + (1 << (k - 1)) 不越界。
  • 查询时区间长度计算错误：应为 len = R - L + 1。
  • 查询时第二个区间的起始索引计算错误：应为 R - (1 << k) + 1。
  • 对数 k 计算错误或效率低下。
  • 数组索引从 0 开始还是从 1 开始不一致。

7. 知识延伸与相关应用

ST 表是解决特定 RMQ (区间最值查询) 问题的利器，它的思想也可以应用或与其他算法结合：

ST 表与 LCA (最近公共祖先)

求解树上两个节点的最近公共祖先 (LCA) 是一个经典问题。一种高效的方法是：

  1. 通过 DFS (深度优先搜索) 遍历树，记录节点的访问顺序 (欧拉序) 和对应深度。
  2. 问题转化为查询欧拉序中，两个节点第一次出现位置之间的深度最小的节点。
  3. 这正是一个 RMQ 问题！可以在记录节点深度的数组上构建 ST 表，实现 O(1) 的 LCA 查询 (预处理 O(n log n))。
高维 ST 表

ST 表可以扩展到二维甚至更高维度，用于查询矩形区域内的最值等信息。

  • 二维 ST 表预处理复杂度约为 O(N * M * logN * logM)。
  • 二维 ST 表查询复杂度仍为 O(1) (对于幂等操作)。
  • 空间复杂度也相应增加 O(N * M * logN * logM)。

实现相对复杂，但在特定静态二维查询场景下有效。

与其他数据结构对比总结
  • ST 表：最适合静态数组的幂等区间查询，查询速度最快 (O(1))，但不能修改，空间开销大。
  • 线段树：功能更通用，支持区间查询和区间/单点修改 (均为 O(log n))，空间 O(n)，是动态区间问题的常用选择。
  • 树状数组 (Fenwick Tree)：主要用于高效处理前缀和/差分相关的查询与单点修改 (均为 O(log n))，空间 O(n)，实现常数较小，代码简洁。虽然也能处理某些区间查询，但不如线段树灵活。

选择哪种数据结构取决于问题的具体需求：是否需要修改？查询的操作类型？时间/空间限制？

感谢学习！希望这个教程对你理解和使用 ST 表有所帮助。