一、课上练习

编程练习

1. ST表&RMQ问题：L49920
2. Gcd 区间：L49921

二、知识总结

✨ 核心思想

ST 表（Sparse Table，稀疏表）是一种基于倍增思想的数据结构，用于解决可重复贡献问题的区间查询。所谓可重复贡献，是指运算 op 满足 op(a, a) = a，例如 min、max、gcd 等。

ST 表的核心优势：O(n log n) 预处理，O(1) 查询，非常适合静态数据的区间最值查询（RMQ 问题）。

✨ 算法原理

预处理

定义 f[i][j] 表示从下标 i 开始、长度为 2^j 的区间的最值，即区间 [i, i + 2^j - 1]。

递推关系：将长度为 2^j 的区间拆分为两个长度为 2^(j-1) 的区间：

f[i][j] = min(f[i][j-1], f[i + 2^(j-1)][j-1])

初始条件：f[i][0] = a[i]（长度为 1 的区间就是元素本身）。

查询

对于查询区间 [l, r]，令 k = floor(log2(r - l + 1))，则：

query(l, r) = min(f[l][k], f[r - 2^k + 1][k])

两个长度为 2^k 的子区间可能重叠，但由于运算可重复贡献，结果仍然正确。

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5const int LOG = 18; // log2(200000) ≈ 17.6
6
7int a[MAXN];
8int f[MAXN][LOG]; // f[i][j] = 从i开始长度为2^j的区间最小值
9int lg[MAXN];     // 预处理log2
10
11int n, m;
12
13// 预处理ST表
14void build() {
15    // 预处理log2值
16    lg[1] = 0;
17    for (int i = 2; i <= n; i++) {
18        lg[i] = lg[i / 2] + 1;
19    }
20
21    // 初始化：长度为1的区间
22    for (int i = 1; i <= n; i++) {
23        f[i][0] = a[i];
24    }
25
26    // 倍增递推
27    for (int j = 1; j < LOG; j++) {
28        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
29            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
30        }
31    }
32}
33
34// O(1)查询区间[l, r]的最小值
35int query(int l, int r) {
36    int k = lg[r - l + 1];
37    return min(f[l][k], f[r - (1 << k) + 1][k]);
38}
39
40int main() {
41    ios::sync_with_stdio(false);
42    cin.tie(nullptr);
43
44    cin >> n >> m;
45    for (int i = 1; i <= n; i++) {
46        cin >> a[i];
47    }
48
49    build();
50
51    while (m--) {
52        int l, r;
53        cin >> l >> r;
54        cout << query(l, r) << "\n";
55    }
56
57    return 0;
58}

✨ 执行示例

以数组 a = [3, 1, 4, 1, 5, 9, 2, 6]（下标从 1 开始，n=8）为例：

预处理表 f[i][j]（最小值）：

查询 query(3, 7)：

1. 区间长度 = 7 - 3 + 1 = 5
2. k = floor(log2(5)) = 2，2^k = 4
3. 答案 = min(f[3][2], f[7-4+1][2]) = min(f[3][2], f[4][2]) = min(1, 1) = 1

查询 query(5, 8)：

1. 区间长度 = 8 - 5 + 1 = 4
2. k = floor(log2(4)) = 2，2^k = 4
3. 答案 = min(f[5][2], f[8-4+1][2]) = min(f[5][2], f[5][2]) = min(2, 2) = 2

✨ 解题步骤详解

1. 判断适用性：题目是否为静态区间查询？运算是否可重复贡献（min/max/gcd/按位或/按位与）？
2. 确定数组大小：LOG 取 ceil(log2(n)) + 1 即可。
3. 预处理：先算 lg 数组，再从 j=0 逐层递推到 j=LOG-1。
4. 查询：利用公式直接 O(1) 回答。

常见变形

• 区间最大值：将 min 改为 max。
• 区间 GCD：将 min 改为 __gcd。
• 二维 ST 表：对二维矩阵做两个维度的倍增，支持子矩阵最值查询。

✨ 常见错误

1. 忘记预处理 lg 数组：直接用 log2() 函数会有浮点精度问题，应该预处理整数 log 值。
2. 数组越界：递推时 i + (1 << j) - 1 必须不超过 n，否则访问非法内存。
3. 对不可重复贡献运算使用 ST 表：区间求和不能用 ST 表（重叠部分会被重复计算），应使用前缀和或树状数组。
4. LOG 设置过小：导致大区间查询时 k 值越界。
5. 下标从 0 还是从 1 开始混淆：统一下标风格，避免 off-by-one 错误。

✨ 算法评价

优点：

• 查询极快，常数小
• 实现相对简单

缺点：

• 不支持修改操作（静态数据结构）
• 只能处理可重复贡献问题
• 空间是普通数组的 log n 倍

适用场景：静态 RMQ、LCA 的 Euler Tour + RMQ 解法、需要大量最值查询的题目。

三、课后练习

编程练习

1. Balanced Lineup G：L49922