ST 表 (Sparse Table)：静态区间、重叠覆盖与倍增查询

上一讲的单调队列，窗口是一路往右走的。如果查询顺序变成 [2,6]、[1,3]、[4,7]，已经弹掉的数可回不来了。

但题目又给了我们一个好消息：数组从头到尾都不变，只需要反复查询最大值。 能不能先花点时间准备，把之后的查询变得特别快？

ST 表干的就是这件事：提前记住长度为 1、2、4、8……的区间答案，询问来了，挑两块拼一下。

一、ST表 (Sparse Table) 核心定义

ST表是一种用于解决可重复贡献问题（如 RMQ，即区间最值查询问题）的数据结构。它不支持修改操作，但能在极短的时间内回答区间查询。本讲的 st[j][i] 存的是：从下标 $i$ 开始、长度为 $2^j$ 的区间中，最大值所在的下标。要读出数值，写 a[st[j][i]]。

通俗理解： “用两块板子盖住水洼”。假设你要找一段水洼里的最高点，你手里有各种长度为 $2$ 的整数次幂的木板。你只需要挑两块长度恰好能覆盖整个水洼的木板，一块从左边盖起，一块从右边贴齐。虽然中间有重叠，但在求最大值时，“被检查两次”完全不影响最终找出的最高点。

二、核心原理与推导 (State Transition & Query)

1. 预处理原理：状态转移与倍增拆分

利用倍增思想，长度为 $2^j$ 的区间，可以严格平分为两个长度为 $2^{j-1}$ 的相邻子区间：

前半段： 起点为 $i$ ，长度为 $2^{j-1}$ 。对应状态为 st[j-1][i]。
后半段： 起点为前半段的末尾加一，即 $i + 2^{j-1}$ ，长度同样为 $2^{j-1}$ 。对应状态为 st[j-1][i + 2^{j-1}]。

整个大区间的最大值，必然产生于这两个子区间的最大值之中。因此状态转移即为比较这两个子区间极值的大小，并继承较大者所在的下标：

st[j][i] = \begin{cases} st[j-1][i] & \text{if } a[st[j-1][i]] > a[st[j-1][i + 2^{j-1}]] \\ st[j-1][i + 2^{j-1}] & \text{otherwise} \end{cases}

预处理通过两层循环基于动态规划自底向上填表，时间复杂度为 $O(N \log N)$ 。

2. 查询原理： $O(1)$ 的重叠覆盖

假设需要查询的区间为 $[l, r]$ ，区间长度为 $len = r - l + 1$ 。

我们需要找到满足 $2^k \le len$ 的最大整数 $k$ 。利用内置函数 __lg(len) 可以在常数时间内求出该向下取整的对数值。

确定了 $k$ 之后，使用两段长度为 $2^k$ 的区间分别贴合查询区间的左边界和右边界：

左覆盖块： 从 $l$ 开始向右延伸 $2^k$ ，区间为 $[l, l + 2^k - 1]$ ，对应的状态为 st[k][l]。
右覆盖块： 从 $r$ 倒退向左延伸 $2^k$ ，区间为 $[r - 2^k + 1, r]$ ，对应的状态为 st[k][r - 2^k + 1]。

重叠证明：

因为 $k = \lfloor \log_2(len) \rfloor$ ，所以有：

2^k \le len < 2^{k+1}

两块的总长度是 $2^{k+1}>len$ ，分别贴住左右边界后，中间不会漏。重叠也没关系，最大值多看一遍还是那个最大值，所以查询只需比较两块的答案。

3. 两块到底怎么选？

拿 a=[4,2,7,3,6,5,1,8] 查询 [2,7]，长度是 6，取 $k=2$ ，每块长度为 4：

块	覆盖的位置	区间内的数	最大值
左边贴齐	`[2,5]`	`2,7,3,6`	7
右边贴齐	`[4,7]`	`3,6,5,1`	6

两块合起来正好覆盖 [2,7]，答案是 $\max(7,6)=7$ 。中间的 3 和 6 被看了两遍，丝毫不影响答案。

ST 表预处理与重叠覆盖的 RMQ 查询

那求和能不能照搬？看看 [1,2,3]：两块 [1,2] 和 [2,3] 的和加起来是 8，而整段和明明是 6，中间的 2 被重复加了。所以这套两块重叠查询适合 max、min、gcd 等，不直接用于区间求和。

三、模板实战：P3865

洛谷 P3865【模板】ST 表 & RMQ 问题给出一个不修改的数组，多次询问区间最大值。下面就是本讲的完整实现。

初始化 st[0][i]=i，因为长度为 1 的区间只能选自己。建表时先填短区间，再拼长区间；查询时 __lg(r-l+1) 帮我们找到合适的层。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int n,m,a[N],st[20][N];
void build(){
    for(int i=1;i<=n;++i)st[0][i]=i;
    for(int j=1;(1<<j)<=n;++j)
        for(int i=1;i+(1<<j)-1<=n;++i){
            if(a[st[j-1][i]]>a[st[j-1][i+(1<<(j-1))]])
                st[j][i]=st[j-1][i];
            else
                st[j][i]=st[j-1][i+(1<<(j-1))];
        }
}
int query(int l,int r){
    int k=__lg(r-l+1),x=st[k][l],y=st[k][r-(1<<k)+1];
    if(a[x]>a[y]) return a[x];
    else return a[y];
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    build();
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<'\n';
    }
    return 0;
}

四、进阶：哪些操作能用 ST 表？

刚刚我们在求区间最大值时，用到了两块有重叠的区间拼接。这个技巧能生效的灵魂前提是：重复计算同一个数，不影响最终答案。

这种性质在数学上叫“幂等性”（ $x \circ x = x$ ）。只有既满足结合律（可以一块一块分段算），又满足可重复贡献的操作，才能愉快地使用 ST 表。

1. 能用 ST 表的好兄弟

区间 GCD（最大公约数）： $\gcd(x, x) = x$ 。假如求 [12, 18, 24] 的最大公约数，两块覆盖是 [12, 18] 和 [18, 24]，分别得出 6 和 6，再求一次 $\gcd(6, 6)$ 还是 6，完全正确。
按位与 (&) / 按位或 (|)： $x \ \& \ x = x$ ， $x \ | \ x = x$ 。位运算也经常结合 ST 表进行 $O(1)$ 的区间询问。

2. 为什么区间和不行？（可结合不等于可重叠）

区间和满足结合律： $(a+b)+c = a+(b+c)$ ，这保证了我们可以把大区间拆成小分块相加。
但它不满足可重复贡献： $x + x \neq x$ 。像 [1, 2, 3] 的两块 [1, 2] 和 [2, 3] 加起来是 $3+5=8$ ，中间的 2 被加了两次，答案就错了。因此求和只能用老老实实不重叠的分块，比如前缀和、树状数组等。

五、选学：二维 ST 表的降维打击

如果题目给的是一个二维矩阵，让你求某个子矩形里的最大值，还能用 ST 表吗？能，只不过原本的线段变成了矩形。我们需要在长和宽两个方向上都做倍增。

1. 状态定义与空间账本

状态长成了四维：st[i][j][x][y] 表示以坐标 $(x, y)$ 为左上角，向下高 $2^i$ ，向右宽 $2^j$ 的矩形区域内的最大值。

算算空间账本：如果矩阵是 $N \times M$ （比如 $1000 \times 1000$ ）。 $i$ 和 $j$ 的最大值大约是 $\approx 10$ 。四维数组元素个数是 $10 \times 10 \times 1000 \times 1000 = 10^8$ 个。如果存 int，大约占用 400 MB 内存！很多比赛的限制只有 256 MB，强行开数组直接就超限了（MLE）。

所以二维 ST 表极其耗费空间，往往只能应对 $500 \times 500$ 左右的数据，或者你需要非常小心地调整维度顺序来优化缓存。用之前一定要看一眼题目的空间限制。

2. 四块盖积木查询

一维查询是用两块线段贴住左右端点。二维查询的物理意义如出一辙：用四块同样大小的矩形，分别贴住要查询区域的左上、右上、左下、右下四个角。

假设我们要查左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$ 的矩阵最大值：长为 $len_x = x_2 - x_1 + 1$ ，宽为 $len_y = y_2 - y_1 + 1$ 。算一下能完全盖住这两个边长，但又不会超出去的积木块尺寸：k1 = __lg(len_x), k2 = __lg(len_y)。

这四块中间有大量重叠，但在求最值的幂等性面前，重叠多少遍都没关系。我们直接把四块拼起来取最大值：

// 二维 ST 表的 O(1) 拼图查询片段（依赖已初始化的四维 st 数组）
int query_2d(int x1, int y1, int x2, int y2) {
    int k1 = __lg(x2 - x1 + 1);
    int k2 = __lg(y2 - y1 + 1);
    
    // 算一算右边和下边积木块的起始坐标
    int rx = x2 - (1 << k1) + 1;
    int ry = y2 - (1 << k2) + 1;
    
    // 提取四块积木，分别贴在四个角上
    int max1 = st[k1][k2][x1][y1]; // 左上角
    int max2 = st[k1][k2][rx][y1]; // 左下角
    int max3 = st[k1][k2][x1][ry]; // 右上角
    int max4 = st[k1][k2][rx][ry]; // 右下角
    
    return max({max1, max2, max3, max4});
}

至于预处理，其实就是在一维 ST 表的基础上再套一层循环。横着拼完再竖着拼。懂了重叠覆盖的本质，升维后也只是按部就班地铺板子而已。

六、什么时候把它拿出来？

数组不改、反复查区间最值，先想 ST 表。预处理 $O(n\log n)$ ，查询 $O(1)$ ，空间 $O(n\log n)$ 。

若所有窗口依次向右滑，单调队列更省；若题目开始修改数组，就不能直接沿用这些预处理好的答案了。下一讲先从最常见的“单点加、区间求和”出发，认识树状数组。

写之前确认两件事：st 存的是值还是下标？两块重叠会不会重复计算出错误的答案？想清楚这两点，代码就很好记了。

ST 表