《梦溪笔谈·C++》卷四十四：ST 表 - 静态区间最值

前言

ST 表，是静态区间最值的 $O(1)$ 方法。就是在数组不改变的情况下，任意区间的最大值（或最小值、GCD、LCM）都能通过一次查询得到。

上次的 ST 表 不是很好，所以翻新。

---

倍增

这是 ST 表用到的思路，但用处不大。就像哈夫曼树用了贪心思想一样。

倍增 详情

（来自 DeePseek）

字面意思，每次成倍增长。通过 $2^k$ 的答案计算 $2^{k+1}$ 的答案。从而把线性时间优化到对数级别。经典的算法有：LCA、ST 表等。

前缀和

虽然前缀和跟 ST 表没有直接联系，但是思维类似。

前缀和 详情

前缀和是在数组内容不改变 $O(1)$ 时间求任意区间和的方法。或者是任意区间差、区间异或、区间积。

一段长度为 $n$ 的序列 $a$。

定义

定义 $s_i$ 为 $a_1$ 到 $a_i$ 的和。例如 $a$ 为 $\{1,1,1,1,1\}$，那么 $s$ 就为 $\{1,2,3,4,5\}$。

初始化

通过递推（$s_i=s_{i-1}+a_i$）可以在 $O(n)$ 求出 $s$。

查询

要查找 $[l,r]$ 区间的和，只需要用 $[1,r]$ 的和减去 $[1,l-1]$ 的和。

复杂度

• 时间复杂度：
  • 初始化：$O(n)$
  • 查询：$O(1)$
• 空间复杂度：$O(n)$

ST 表问题模板

一个长度为 $n$ 的序列 $a$。有 $q$ 次询问，每次询问给出 $l$ 和 $r$。求序列 $a$ 的 $[l,r]$ 区间的最大值。

ST 表的线性退化

线性退化 详情

定义

考虑使用区间 DP。定义 $dp_{i,j}$ 表示区间 $[i, i + j - 1]$ 的最大值。即从 $a_i$ 开始往后数 $j$ 个数的最大值。

初始化

$dp_{i,1}$ 表示从 $a_i$ 开始往后数 $1$ 个数中的最大值，自然就是 $a_i$。

for i = 1 to n:
    dp[i][1] = a[i]

转移

可以把区间 $[i, i + j - 1]$ 转化为 $[i, i + j - 2]$ 和 $[i + j - 1, i + j - 1]$：

for j = 2 to n: # 枚举区间长度
    for i = 1, i + j - 1 <= n: # 枚举起点
    # 终点(i + j - 1) 不能超过 n
        dp[i][j] = max(dp[i][j - 1], a[i + j - 1])

时间复杂度：$O(n^2)$；
空间复杂度：$O(n^2)$。

查询

询问区间 $[l,r]$ 的最大值，起点是 $l$，区间长度是 $r-l+1$。因此区间 $[l,r]$ 的最大值为 $dp_{l,r-l+1}$。

dp[l][r - l + 1]

分析

初始化时间 $O(n^2)$，查询 $O(1)$。适合 $n$ 在 $10^4$ 左右使用（？可能会超空间）。ST 表和这个极其类似，只是利用了倍增的思想，初始化时间优化到 $O(n\log n)$。

$\log_2$ 函数

log2 函数 详情

$\log_2 n$，即是 $2$ 的多少次方为 $n$。若 $x=\log_2 n$，那么 $2^x=n$。

ST 表

正文开始

ST 表，是静态区间最值的 $O(1)$ 方法。就是在数组不改变的情况下，任意区间的最大值（或最小值、GCD、LCM）都能通过一次查询得到。

以下内容以最大值为例。其他只需要把求较大值改为相应计算。

定义

定义 $f_{i,j}$ 表示 $a$ 的 $[i,i+2^j-1]$ 区间的最大值。即从 $a_i$ 往后数 $2^j$ 个数中的最大值。$2^j$ 增长非常快，所以数组的第二维通常很小（$\log_2 n$）。

例如 $a=\{1,2,3,4,5\}$。要求 $[2,3]$ 区间的最大值，区间长度为 $2$，可以直接在 $f_{2,1}$ （从 $a_2$ 开始往后数 $2^1=2$ 个数）得到。

那要求 $[2,4]$ 区间的最大值呢？区间长度为 $3$。用 $2^1=2$ 会少算一个数，用 $2^2=4$ 又会多算一个数。此时就可以把长度为 $3$ 的区间转化为 $2$ 个长度为 $2$ 的重叠的区间：

这就是 ST 表初始化和查询的思路。

初始化

类似 DP $O(n^2)$ 版：$dp_{i,1}$ 表示从 $a_i$ 开始往后数 $1$ 个数，即 $dp_{i,1}=a_i$。

$f_{i,0}$ 表示从 $a_i$ 开始往后数 $2^0=1$ 个数，也为 $a_i$。所以 $f_{i,0}=a_i$。

for i = 1 to n:
    st[i][0] = a[i]

转移

如定义中内容所说，剩下的枚举区间长度、枚举起点几乎和 DP 版一样。注意外层循环 $j$ 枚举的不直接是区间长度，$2^j$ 才是区间长度。

在计算区间长度为 $2^j$ 的区间的最大值时，可以分为两个长度为 $2^{j-1}$ 区间，取最大值。

枚举 $j$ 时，不应超过 $\log n$。也不需要大一点点。因为在查询时会通过两个区间补全。

for j = 1 to log2(n): # 2^j 为区间长度
    for i = 1, i + (1 << j) - 1 <= n: # 枚举区间起点
    # 终点(i + (1 << j) - 1) 不能超过 n
        st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])

时间复杂度：$O(n\log n)$；
空间复杂度：$O(n\log n)$。

查询

要查询区间 $[l,r]$ 的最大值。区间起点是 $l$，区间长度是 $r-l+1$。

如图，查询 $[1,3]$ 区间的最大值，就可以分成 $[1,2]$ 和 $[2,3]$ 两个区间的最大值。这两个小区间的长度都是 $2^j$，因此可以直接在 ST 表里找到。

那如何确定这两个区间的起点和长度呢？

ST 表里区间长度都是 $2^j$，因此这两个区间都不能超过 $r-l+1$，且是 $2^k$ 次方。这个 $2^k$ 不能超过 $r-l+1$，此时就要搬出 $\log_2$ 函数了。若 $k=\log_2(r-l+1)$，那么 $k$ 是一个小数，在 ST 表里可没有小数的下标。如果将 $k$ 向下取整，那么 $2^k$ 就刚好比 $r-l+1$ 小一些。此时就可以在 ST 表里找到对应内容了。

前一个区间的起点肯定是从 $l$ 往后数 $2^k$ 个数，对应 $f_{l,k}$。那另一个区间自然就是从 $r$ 往前数 $2^k$ 个数。根据终点（$r$）和区间长度（$2^k$），可以求出起点是 $r-k+1$。

k = floor(log2(r - l + 1))
max(st[l][k], st[r - k + 1][k])

如何求 $\log_2$

既然 $2^x$ 不超过 $n$，就自然想到二分。但是二分的效率（相较于 $O(1)$）非常低，是 $O(\log n)$ 的时间。

也可以使用 <cmath> 库里的 log2() 函数，但是这样（在这种只需要 $1$ ~ $n$ 且大量使用的情况下）效率也不够高。

$\lfloor\log_2n\rfloor=\lfloor\log_2\frac{n}{2}\rfloor+1$。因此我们可以直接递推求出 $1$ ~ $n$ 所有的 $\log_2$ 函数的值。

log[0] = -1
for i = 1 to n:
    log[i] = log[i >> 1] + 1

总结

初始化时间：$O(n\log n)$，查询时间：$O(1)$。

伪代码：

# 定义略
def init(): # 初始化
    log[0] = -1
    for i = 1 to n:
        log[i] = log[i >> 1] + 1
        st[i][0] = a[i]

    for j = 1 to log[n]: # 区间长度
        for i = 1, i + (1 << j) - 1 <= n: # 起点
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]

def que(l, r): # 查询
    k = log[r - l + 1]
    return max(st[l][k], st[r - (1 << k) + 1][k])