第 78 课 - 稀疏表

模块：高级数据结构
难度：advanced
标签：sparse-table, rmq, preprocess, query
上一课：伸展树
下一课：后缀数组

1. 学习目标

完成本课学习后，你将能够：

理解问题：清晰描述区间最值查询问题及其朴素解法的局限性。
掌握核心思想：阐述稀疏表如何通过预处理将查询时间复杂度降至 O(1)。
实现算法：独立编写一个静态数组的稀疏表，用于快速回答区间最小/最大值查询。
评估优缺点：分析稀疏表在时间、空间复杂度上的特点，并了解其适用场景。

2. 核心概念

区间最值查询是算法中一个非常经典的问题。给定一个长度为 n 的静态数组（不会修改），你需要进行多次查询，每次询问一个区间 [L, R] 内的最小值（或最大值）。

朴素做法：每次查询都遍历区间，时间复杂度为 O(n)。如果查询次数 q 很多，总复杂度为 O(nq)，对于大规模数据将非常缓慢。
更高效的需求：我们能否付出一些预先计算（预处理）的代价，来让每次查询变得极快？

稀疏表正是为解决这个问题而生的“表格工具”。它的核心思想是 “倍增”。

2.1 预处理：构建“答案表格”

想象一下，我们预计算并存储所有长度为 2 的幂次（1， 2， 4， 8， ...）的区间的最值。例如，对于数组 A，我们计算并存储：

dp[i][0]：表示以 i 为起点，长度为 2^0 = 1 的区间的最值（其实就是 A[i]）。
dp[i][1]：表示以 i 为起点，长度为 2^1 = 2 的区间的最值。
dp[i][k]：表示以 i 为起点，长度为 2^k 的区间的最值。

关键的递推关系非常精妙：一个长度为 2^(k+1) 的区间，可以拆分为两个长度为 2^k 的、有重叠部分的子区间。

长度 2^(k+1) = 长度 2^k + 长度 2^k (重叠)
[  i ... i + 2^k - 1, ... i + 2^(k+1) - 1 ]
       ^---子区间1---^
               ^---子区间2---^

因此，我们可以通过以下公式来填充表格： dp[i][k+1] = min(dp[i][k], dp[i + 2^k][k]) (以最小值为例)

这个预处理的时间复杂度是 O(n log n)，空间复杂度也是 O(n log n)。

2.2 查询：利用“已知答案”拼接

查询区间 [L, R] 的最值时，我们不必逐个遍历。设 len = R - L + 1。我们找到一个最大的 k，使得 2^k <= len（即 k = floor(log2(len))）。

此时，区间 [L, R] 一定可以被两个长度为 2^k 的、有重叠的区间完全覆盖：

区间一：[L, L + 2^k - 1]
区间二：[R - 2^k + 1, R]

这两个区间的并集恰好覆盖 [L, R]。而它们的答案在预处理时已经存在于 dp[L][k] 和 dp[R - 2^k + 1][k] 中。因此，最终答案就是： min(dp[L][k], dp[R - 2^k + 1][k])

为什么允许重叠？ 因为我们是求最值，重叠区间不会影响最值结果。这是稀疏表适用于可重复贡献问题（如 RMQ, 区间 GCD）的关键。

3. 代码示例

下面是一个完整的 Python 实现，用于回答区间最小值查询。

import math

class SparseTable:
    def __init__(self, arr):
        """
        初始化稀疏表
        :param arr: 输入数组 (列表)
        """
        n = len(arr)
        # 计算 log2(n) 向下取整，确定表格的列数 (k的范围)
        max_k = math.floor(math.log2(n)) + 1
        
        # 初始化 dp 表: dp[i][k] 存储从 i 开始，长度为 2^k 的区间的最小值
        self.dp = [[0] * max_k for _ in range(n)]
        
        # 第0列 (k=0): 长度为1的区间，最小值就是数组元素本身
        for i in range(n):
            self.dp[i][0] = arr[i]
        
        # 填充表格：按列(k)填充，因为计算 dp[i][k] 需要 dp[i][k-1] 和 dp[i + 2^(k-1)][k-1]
        for k in range(1, max_k):
            # 计算 2^(k-1)
            step = 1 << (k-1)
            # i 的上限：需要保证 i + 2^k - 1 < n，即 i <= n - 2^k
            for i in range(n - (1 << k) + 1):
                # 状态转移方程：取左右两个子区间的最小值
                self.dp[i][k] = min(self.dp[i][k-1], self.dp[i + step][k-1])
    
    def query(self, L, R):
        """
        查询区间 [L, R] 的最小值
        :param L: 左闭区间下标
        :param R: 右闭区间下标
        :return: 区间最小值
        """
        # 计算区间长度
        length = R - L + 1
        # 找到最大的 k，使得 2^k <= length
        k = int(math.log2(length))
        # 取两个覆盖区间的最小值
        return min(self.dp[L][k], self.dp[R - (1 << k) + 1][k])

# 示例用法
if __name__ == "__main__":
    data = [3, 1, 4, 1, 5, 9, 2, 6]
    st = SparseTable(data)
    
    print(f"原始数组: {data}")
    print(f"查询区间 [0, 3] 的最小值: {st.query(0, 3)}")  # 预期: 1
    print(f"查询区间 [2, 5] 的最小值: {st.query(2, 5)}")  # 预期: 1
    print(f"查询区间 [4, 7] 的最小值: {st.query(4, 7)}")  # 预期: 2

运行输出：

原始数组: [3, 1, 4, 1, 5, 9, 2, 6]
查询区间 [0, 3] 的最小值: 1
查询区间 [2, 5] 的最小值: 1
查询区间 [4, 7] 的最小值: 2

4. 实践练习

练习 1：基础实现

给定一个数组 arr = [7, 2, 9, 5, 1, 8, 3, 6]，请根据上述代码模板，手动计算或编程得到：

dp[0][1] (即从索引0开始，长度为2的区间最小值) 的值。
dp[2][2] (即从索引2开始，长度为4的区间最小值) 的值。
查询区间 [1, 4] 的最小值，演示查询过程。

练习 2：修改与对比

现在假设数组可能会被修改（单点更新）。请思考：

稀疏表是否还能高效地支持这种操作？为什么？
如果不能，哪种其他的数据结构（如线段树）更适合处理动态数组的区间最值查询？请简述原因。

练习 3：思维拓展

考虑问题：给定一个数组，多次查询区间 [L, R] 内所有元素的总和。

稀疏表（基于“可重复贡献”原理）能否直接用于解决这个问题？请解释你的答案。
如果不能，你会使用哪种前缀和思想来在 O(1) 时间内回答每次求和查询？

5. 常见错误

混淆预处理与查询的复杂度：
- 错误：“稀疏表查询是 O(1) 的，所以它总是最好的选择。”
- 正确：稀疏表的预处理是 O(n log n)，适合静态数组的多次查询。如果数组会频繁修改，单次修改的代价很高（需要重建整个表），此时它不如树状数组或线段树。
区间覆盖计算错误：
- 错误：查询时，错误地计算第二个区间的起始点。例如，将 R - (1 << k) + 1 写成 R - (1 << k)。
- 正确：牢记公式，第二个区间的起始位置是 R - 2^k + 1，这样才能保证它与第一个区间共同覆盖 [L, R]。
log2 的精度与类型问题：
- 错误：在需要整数索引 k 的地方，直接使用浮点数计算结果而未进行转换。
- 正确：查询时，k = int(math.log2(length)) 确保 k 是整数。或者使用位运算 (length).bit_length() - 1 更高效。
适用问题类型误解：
- 错误：试图用稀疏表计算区间“平均值”、“和”（虽然和可以用前缀和更优）等不可重复贡献的运算。
- 正确：稀疏表只适用于可重复贡献问题，即 f(a, a, b) = f(a, b) 的运算，如 min, max, gcd。

6. 小结

本节课我们学习了用于高效解决 静态区间最值查询 问题的强大数据结构——稀疏表。

核心思想：利用 “倍增” 和 预处理，预先计算并存储所有长度为 2 的幂次区间的答案。
构建：时间复杂度 O(n log n)，空间复杂度 O(n log n)。递推公式 dp[i][k] = f(dp[i][k-1], dp[i + 2^(k-1)][k-1])。
查询：时间复杂度 O(1)。关键步骤是找到 k = floor(log2(R-L+1))，然后通过 min(dp[L][k], dp[R-2^k+1][k]) 得到答案，利用了区间的重叠覆盖。
局限性：不支持动态修改（单点更新代价高），仅适用于可重复贡献的运算（如 RMQ, 区间 GCD）。

稀疏表是理解算法设计中“用空间换时间”和“预处理”思想的绝佳范例，为后续学习更复杂的数据结构（如后缀数组）打下基础。

练习编辑器

rust