ST 表

一句话算法

ST 表预处理所有长度为 $2^k$ 的区间，查询时用两个可重叠的区间覆盖答案区间。

问题模型

给定一个长度为 $n$ 的静态数组：

有 $q$ 次查询，每次给出区间 $[l,r]$，要求求出：

“静态”表示数组不会修改。如果有修改操作，应优先考虑线段树或树状数组。

核心直觉

ST 表只做两件事：

1. 预处理每个起点、每种 $2^k$ 长度的区间信息；
2. 查询时选一个不超过查询长度的最大 $2^k$，用左端一段和右端一段覆盖整个区间。

$2^k$ 的块长有多大？ $k$ 每增加 1，块长翻倍——和倍增跳跃的步长是同一个思想：

k=0 (2^0=1)  |---|                                st[i][0] = a[i]
k=1 (2^1=2)  |-----------|                        st[i][1] = max(a[i], a[i+1])
k=2 (2^2=4)  |-----------------------|            st[i][2] = max(a[i..i+3])

查询时怎么覆盖？ 例如查询长度为 6，最大不超它的 $2^k$ 是 $4$（$k=2$）：

+---+ +---+ +---+ +---+ +---+ +---+
| l | |l+1| |l+2| |l+3| |l+4| | r |
+---+ +---+ +---+ +---+ +---+ +---+

left  |---------------|          st[l][k]
right        |---------------|   st[r-2^k+1][k]
                  ^ overlap
answer = max(left, right)   (overlap OK: max(x,x)=x)

这两个区间会重叠，但求最大值时重复计算不影响结果，因为：

这就是 ST 表能做到 $O(1)$ 查询的关键。

状态设计

定义：

• $st[i][k]$, 表示从位置 $i$ 开始，长度为 $2^k$ 的区间 $[i, i+2^k-1]$ 最大值
• 边界： $st[i][0]=a_i$

因为长度为 $1$ 的区间最大值就是它自己。

状态转移

长度为 $2^k$ 的区间可以一切为二，用两个长度为 $2^{k-1}$ 的块拼出整块（以 $k=2$ 为例）：

k=2  [i ................. i+3]
      |-----------------------|   st[i][2]

k=1  [i ..... i+1] [i+2 .. i+3]
      |-----------|  |-----------|
      st[i][1]      st[i+2][1]

st[i][2] = max( st[i][1], st[i+2][1] )

一般形式：$st[i][k]=\max(st[i][k-1],st[i+2^{k-1}][k-1])$。

查询方法

查询 $[l,r]$ 时，令：

取：

那么 $2^k \le len < 2^{k+1}$，所以两个长度为 $2^k$ 的区间一定能覆盖 $[l,r]$：

和：

答案为：

算法步骤

1. 读入数组。
2. 预处理 lg[i] = floor(log2(i))。
3. 初始化 st[i][0] = a[i]。
4. 按 k = 1..log n 递推所有长度为 $2^k$ 的区间。
5. 每次查询时用 lg[r-l+1] 找到最大可用长度。
6. 合并左端和右端两个区间的答案。

算法证明

核心不变量：构建完第 $k$ 层后，st[i][k] 等于区间 $[i,i+2^k-1]$ 的最大值。

1. 边界正确

   当 $k=0$ 时，区间长度为 $1$，最大值就是 $a_i$。

2. 转移正确

   长度为 $2^k$ 的区间被完整拆成两个长度为 $2^{k-1}$ 的相邻区间。整个区间的最大值一定是两个子区间最大值中较大的那个。

3. 查询覆盖正确

   对任意长度 len，取 $k=\lfloor\log_2 len\rfloor$，有：

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

   因此：

   $$2 \times 2^k \ge len$$

   左端长度 $2^k$ 和右端长度 $2^k$ 的区间一定覆盖整个查询区间。

4. 重叠不影响结果

   查询使用的是最大值运算。重叠部分即使被计算两次，也满足：

   $$\max(x,x)=x$$

   所以查询结果正确。

因此 ST 表能正确回答静态区间最大值查询。

复杂度分析

设数组长度为 $n$，查询次数为 $q$。

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

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

        #include <bits/stdc++.h>
using namespace std;

// ST 表：预处理所有长度为 2^k 的区间最值，O(1) 查询静态 RMQ
// st[i][k] = 从 i 开始、长度为 2^k 的区间最大值
// 查询时用两个可重叠的 2^k 区间覆盖 [l, r]（重叠不影响 max/min/gcd 等幂等运算）
struct SparseTable {
    int n = 0;
    vector<int> lg;               // lg[x] = floor(log2(x))，查一次取整
    vector<vector<int>> st;       // st[i][k] = max( a[i..i+2^k-1] )

    void build(const vector<int> &a) {
        n = (int)a.size() - 1;    // a 使用 1-indexed

        // 预处理 log2 表，避免每次查询重复计算
        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; i++)
            lg[i] = lg[i / 2] + 1;

        int max_log = lg[n] + 1;  // 最大 k = floor(log2(n))
        st.assign(n + 1, vector<int>(max_log, 0));

        // k=0：长度为 1 的区间就是自己
        for (int i = 1; i <= n; i++)
            st[i][0] = a[i];

        // k>0：长度为 2^k 的区间 = 左 2^{k-1} + 右 2^{k-1}
        for (int k = 1; k < max_log; k++) {
            int len = 1 << k;          // 当前区间长度 2^k
            int half = len >> 1;       // 半长 2^{k-1}
            for (int i = 1; i + len - 1 <= n; i++)
                st[i][k] = max(st[i][k - 1], st[i + half][k - 1]);
        }
    }

    // 查询 [l, r] 最大值：取 k = floor(log2(r-l+1))，两部分重叠覆盖
    int query(int l, int r) const {
        int k = lg[r - l + 1];         // 最大不超过区间长的 2^k 的 k
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    SparseTable table;
    table.build(a);

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << table.query(l, r) << "\n";
    }

    return 0;
}
    

测试用例

输入：

5 3
5 2 3 1 6
1 2
2 3
2 5

输出：

5
3
6

应用分类详解

ST 表的本质是：静态数组上，对可重复贡献的区间信息做倍增预处理。只要题目中没有修改操作，并且有大量区间最值类查询，就应该想到 ST 表。

一、静态 RMQ

典型模式： 数组不修改，多次查询区间最大值或最小值。

识别信号： 出现“静态序列”“多次询问”“区间最大/最小”。

核心建模： st[i][k] 维护从 i 开始长度为 $2^k$ 的区间最值。

二、区间 GCD / AND / OR

典型模式： 查询区间内某种幂等运算结果。

识别信号： 运算满足 op(x, x) = x，且数组静态。

核心建模： 把 max 换成对应的 op，查询仍然用两个重叠区间。

三、LCA 转 RMQ

典型模式： 树上 LCA 转成欧拉序上的深度最小值查询。

识别信号： 静态树，多次询问最近公共祖先。

核心建模： DFS 得到欧拉序，两个点第一次出现位置之间的最小深度节点就是 LCA。

经典例题

1. luogu-P3865

ST 表模板题。数组静态，询问区间最大值。

2. luogu-P2880

同时查询区间最大值和最小值。可以建两个 ST 表，答案为 max - min。

3. luogu-P3379

最近公共祖先模板题。除了倍增 LCA，也可以用欧拉序加 RMQ 的方式求解。

参考

• 倍增思想。
• 静态 RMQ 问题。