稀疏表 (Sparse Table)

引言：“零延迟”查询

想象你有一组固定的数据，比如历史天气记录。你需要回答成千上万个问题，比如：“第 X 天到第 Y 天之间的最低气温是多少？”

如果数据永不改变，为什么还要满足于 $O(\log N)$（线段树）呢？ 稀疏表 (Sparse Table) 利用动态规划预计算重叠区间，允许它在常数时间 $O(1)$ 内回答任何区间最值查询 (RMQ)。

算法要解决什么问题？

• 输入： 一个静态数组（不允许更新）。
• 输出： 任意区间 [L, R] 内的最小值或最大值。
• 承诺： 理论上最快的查询速度 ($O(1)$)。

核心思想 (直觉版)

逻辑就是 “倍增”：

1. 预计算所有长度为 1, 2, 4, 8, …（2 的幂）的区间的最小值。
2. 将其存储在表 st[i][j] 中，含义为：“从索引 i 开始，长度为 $2^j$ 的区间最小值”。
3. 重叠的魔力： 任何长度的区间 [L, R] 都可以被 两个重叠的、长度为 2 的幂的区间完全覆盖。例如，长度为 7 的区间可以被两个长度为 4 的重叠区间覆盖。
4. 因为 min(A, B) 操作即使 A 和 B 有重叠，结果也是正确的，所以我们只需取这两个预计算值的最小值。

算法是如何工作的？

1. 预处理： 使用动态规划：st[i][j] = min(st[i][j-1], st[i + 2^{j-1}][j-1])。耗时 $O(N \log N)$。
2. 查询：
   • 计算 $k = \lfloor \log_2(R - L + 1) floor$。
   • 结果 = min(st[L][k], st[R - 2^k + 1][k])。

典型业务场景

• ✅ 历史数据分析： 在固定的时间序列中查询最值（例如：“2023 年的最大 CPU 负载”）。

• ✅ LCA (最近公共祖先)： 寻找树中 LCA 的标准做法是将树转换为数组，然后使用稀疏表进行 RMQ。

• ✅ 字符串算法： 在后缀数组中寻找两个子串的最长公共前缀 (LCP)。

• ❌ 动态数据： 如果数组中即使只有一个元素发生改变，你也必须重新执行整个 $O(N \log N)$ 的预处理。对于动态数据，请改用 线段树。

性能与复杂度总结

• 查询： $O(1)$。
• 预处理： $O(N \log N)$。
• 空间： $O(N \log N)$，用于存储倍增表。

小结：一句话记住它

“稀疏表是静态数据的‘速度狂人’。它通过预计算 2 的幂次区间，利用重叠特性实现了区间最值的一步查询。”