ST 表

ST 表（Sparse Table）是一种用于解决 静态区间查询 的数据结构。这里的静态，指的是数组内容在查询过程中不会被修改；区间查询，最常见的例子就是：给定一个数组，反复询问某个区间里的最大值或者最小值。

如果每次查询都从左到右扫一遍，那么一次查询就是 $O(n)$。当查询次数很多时，这种做法就会显得很吃力。ST 表做的事情其实很朴素：提前把一些标准长度的区间答案算好，真正查询时直接拼出答案。

##核心思想

ST 表的核心可以用一句话概括：

预处理所有长度为 $2^k$ 的区间答案，然后用这些区间快速回答任意查询。

假设我们要求的是区间最大值，定义：

表示从下标 $i$ 开始，长度为 $2^k$ 的区间中的最大值。也就是说：

比如 st[3][2] 表示从下标 3 开始、长度为 $2^2=4$ 的区间最大值。

这个定义看起来有点绕，但其实就是把很多连续区间按照长度分层保存下来：

text[copy]
k = 0: 长度 1 的区间    [x]
k = 1: 长度 2 的区间    [x x]
k = 2: 长度 4 的区间    [x x x x]
k = 3: 长度 8 的区间    [x x x x x x x x]

每一层只关心一种长度，而这些长度都是 $2$ 的幂次。

##预处理

有了上面的定义，预处理就很自然了。

长度为 $1$ 的区间答案就是数组本身：

长度为 $2^k$ 的区间，可以拆成两个长度为 $2^{k-1}$ 的小区间：

所以状态转移就是：

这一步和动态规划的味道很像：先算小区间，再用小区间拼出大区间。

举个例子，数组为：

text[copy]
a = [1, 3, 2, 7, 9, 11]

如果求区间最大值，那么部分 ST 表可以写成：

以 st[1][2] 为例，它表示区间 [1, 4]，也就是 [3, 2, 7, 9] 的最大值，所以答案是 9。

##查询

ST 表最巧妙的地方在查询。

假设我们要查询区间 [l, r] 的最大值，区间长度为：

取：

也就是说，$2^k$ 是不超过当前区间长度的最大 $2$ 的幂次。接下来，我们用两个长度为 $2^k$ 的区间覆盖 [l, r]：

1. 左边一段：[l, l + 2^k - 1]
2. 右边一段：[r - 2^k + 1, r]

示意图大概是这样：

text[copy]
查询区间：[l --------------------------- r]

左块：    [l ------------]
右块：                  [------------ r]

两个块可能会重叠，但一定能覆盖整个查询区间。

于是查询公式就是：

这里可能会有一个疑问：两个区间重叠了怎么办？

对于最大值来说，重叠完全没关系。因为一个数即使被算了两遍，也不会改变最大值的结果：

最小值同理：

这种性质叫做 幂等性。这也是 ST 表能够做到 $O(1)$ 查询的关键。

还是用刚才的数组举例：

text[copy]
a = [1, 3, 2, 7, 9, 11]

如果查询 [1, 5] 的最大值，区间长度为 5，所以 $k = 2$，对应长度 $2^2 = 4$。

我们取两个长度为 4 的区间：

text[copy]
原区间：[1, 5] => [3, 2, 7, 9, 11]

左块：[1, 4] => [3, 2, 7, 9]
右块：[2, 5] =>    [2, 7, 9, 11]

虽然 [2, 4] 被覆盖了两次，但最大值仍然可以直接取：

##代码实现

下面给出一个 Python 版本，以区间最大值为例。

py[copy]
class SparseTable:
    def __init__(self, nums: list[int]):
        self.n = len(nums)

        # log[i] 表示 floor(log2(i))
        self.log = [0] * (self.n + 1)
        for i in range(2, self.n + 1):
            self.log[i] = self.log[i // 2] + 1

        # m 是 floor(log2(n)) + 1，这样数组下标才能取到最大的 k = floor(log2(n))
        m = self.log[self.n] + 1
        self.st = [[0] * m for _ in range(self.n)]

        for i, x in enumerate(nums):
            self.st[i][0] = x

        for k in range(1, m):
            length = 1 << k
            half = length >> 1
            for i in range(self.n - length + 1):
                self.st[i][k] = max(self.st[i][k - 1], self.st[i + half][k - 1])

    def query(self, l: int, r: int) -> int:
        length = r - l + 1
        k = self.log[length]
        return max(self.st[l][k], self.st[r - (1 << k) + 1][k])

如果要改成区间最小值，只需要把 max 改成 min 即可。

py[copy]
self.st[i][k] = min(self.st[i][k - 1], self.st[i + half][k - 1])
return min(self.st[l][k], self.st[r - (1 << k) + 1][k])

##同时维护区间最小值和最大值

有些题目并不是单独询问区间最大值或者最小值，而是需要同时知道两者。比如要求一个子数组的 极差，也就是：

这时也可以用 ST 表，只不过每个位置不再只存一个数字，而是存一个二元组 (最小值, 最大值)。

两个区间合并时，最小值取两个最小值中的较小者，最大值取两个最大值中的较大者：

py[copy]
def op(a: tuple[int, int], b: tuple[int, int]) -> tuple[int, int]:
    return min(a[0], b[0]), max(a[1], b[1])

完整写法可以这样：

py[copy]
class MinMaxSparseTable:
    def __init__(self, nums: list[int]):
        n = len(nums)
        m = n.bit_length()
        st = [[None] * n for _ in range(m)]
        st[0] = [(x, x) for x in nums]

        for k in range(1, m):
            half = 1 << (k - 1)
            for i in range(n - (1 << k) + 1):
                st[k][i] = op(st[k - 1][i], st[k - 1][i + half])

        self.st = st

    # 查询 [l, r) 左闭右开区间的最小值和最大值
    def query(self, l: int, r: int) -> tuple[int, int]:
        k = (r - l).bit_length() - 1
        return op(self.st[k][l], self.st[k][r - (1 << k)])

    def range_diff(self, l: int, r: int) -> int:
        mn, mx = self.query(l, r)
        return mx - mn

这里用了 Python 的 bit_length() 来计算 $\lfloor \log_2 len \rfloor$，就不需要额外维护 log 数组了。并且代码里采用的是 [l, r) 左闭右开区间，和 Python 切片的习惯保持一致。

这种写法比单独维护最大值稍微抽象一点，但在刷题时很实用：只要合并操作满足 ST 表的要求，就可以把需要维护的信息一起放进状态里。

##适用范围

ST 表很适合下面这类问题：

• 数组不会被修改
• 需要进行大量区间查询
• 查询操作满足幂等性

最典型的就是：

• 区间最大值
• 区间最小值
• 区间 gcd

但 ST 表并不适合所有区间问题。比如区间和就不适合用上面这种查询方式，因为两个块重叠后，重叠部分会被加两次：

所以如果是区间和，通常会优先考虑前缀和；如果数组还会发生修改，就应该考虑线段树、树状数组这类结构。

##复杂度

假设数组长度为 $n$：

• 预处理时间复杂度：$O(n \log n)$
• 单次查询时间复杂度：$O(1)$
• 空间复杂度：$O(n \log n)$

所以 ST 表本质上是用更多的预处理时间和空间，换取非常快的查询速度。对于“数组固定，但查询很多”的场景，这个交换通常是很划算的。

##总结

ST 表其实并不神秘，它就是把区间按照 $2$ 的幂次提前整理好。真正查询时，利用两个足够长的块覆盖目标区间，再借助 max / min / gcd 这类操作的幂等性，在 $O(1)$ 时间内得到答案。

如果用几个关键词记住它，大概就是：静态数组、区间查询、倍增预处理、幂等操作。

##参考

• OI Wiki：ST 表
• CP Algorithms：Sparse Table