ST表（Sparse Table） | 王心俊老师信息学奥赛课件

模块 02

知识探究

先看清「静态 + 大量查询」这个场景的特殊性，再顺着倍增的思路一步步把 st 表搭出来。

①RMQ 问题与四种朴素解法

问题形式化：给定静态数组 a[1..n] 和 q 次询问，每次给出 (l, r)，求 max{a[l..r]}（或 min）。

在 ST 表出现之前，人们用过这些方法：

解法	预处理	单次查询	总复杂度	评价
暴力扫描	无	O(n)	O(nq)	n = q = 10⁵ 时 10¹⁰，超时
稀疏表（ST 表）	O(n log n)	O(1)	O(n log n + q)	本讲主角，静态 RMQ 的最优解
线段树	O(n)	O(log n)	O(n + q log n)	能支持修改，但查询慢一个 log
树状数组	O(n)	O(log n)	O(n + q log n)	适合可减运算（求和），最值不方便
分块 / 块状表	O(n)	O(√n) 或 O(1)	—	常数大，教学价值大于实用

关键观察：ST 表之所以能压到 O(1) 查询，靠的是「静态、无修改」这个前提——正因为数据永远不变，我们才敢把「所有 2^k 长度区间的答案」全部提前算好。这是典型的空间换时间。

❓ 一个自然的疑问：为什么不干脆把所有区间 [l, r] 的答案都预处理出来？那样查询也是 O(1)，而且思路更直白。

答案：因为「所有区间」共有 n(n+1)/2 个，当 n = 10⁵ 时约 5×10⁹ 个——存不下（按 4 字节算需要 20 GB）。而只存「长度为 2 的幂」的区间，只有 n × log n ≈ 1.7×10⁶ 个，完全可以承受。这就是「稀疏」二字的意义：在 O(n²) 和 O(1) 之间，找到一个刚好够用的 O(n log n) 平衡点。

🎬 同一次查询 [3, 7]（数组 9 3 1 7 5 6 0 8）：暴力 vs ST 表

1暴力扫描：从 a[3]=1 出发，逐个比较 1 → 7 → 5 → 6 → 0，共 5 次比较得到 max = 7。区间长 5 就比 5 次，长 10⁵ 就比 10⁵ 次

2ST 表：len = 5，k = lg[5] = 2，一次拿出 st[3][2]（覆盖 [3,6]，值 7）

3再拿出 st[4][2]（覆盖 [4,7]，值 7）

41 次 max 合并 → 答案 7。总计 2 次取表 + 1 次比较，与区间长度无关

5差距从哪来？暴力是「现算」，ST 表是「查表」——预处理时已经把答案塞进表里了。预处理越厚，查询越薄

若查询 q = 10⁵ 次：暴力约 10¹⁰ 次比较（超时），ST 表约 3×10⁵ 次操作（瞬间完成）。查询次数越多，「预处理 + 查表」的优势越大。

②倍增思想：只算 2 的幂次，为什么够用

倍增的核心信念：任何正整数都能唯一分解成若干个 2 的幂之和（这就是二进制）。所以「只掌握长度为 2^k 的信息」并不等于「信息有缺失」。

举个具体的例子，长度 len = 13 = 1101₍₂₎ = 8 + 4 + 1：

图 1：两种「用 2 的幂覆盖区间」的方式

为什么 ST 表选第二种而不是第一种？

第一种（二进制分解）虽然也不重叠，但合并次数是 O(log len)——查询就不可能是 O(1) 了。而且「分解方案」本身还要提前知道 len 的二进制表示。
第二种（两段覆盖）无论区间多长，永远只用两段、永远只做一次合并——这才是 O(1) 查询的来源。代价是必须允许重叠，所以只适用于可重复贡献的运算。

一句话总结：ST 表用「允许重叠」换来了「只用两段」，从而换来了 O(1) 查询。这是整个算法中最狡猾也最漂亮的一步。

💡 倍增在竞赛里还有哪些亲戚？

快速幂：把指数按二进制拆分，a¹³ = a⁸·a⁴·a¹，每次把底数平方 —— 同样是「只算 2 的幂次」。

倍增 LCA：up[u][k] 表示「u 向上跳 2^k 步到达的祖先」，与 ST 表的 st[i][k] 结构完全同构。

倍增 Floyd / 矩阵快速幂：把「走恰好 L 条边」的路径数用 2 的幂次预处理出来。

识别信号：题目里出现「跳 2^k 步」「长度为 2^k 的区间」「快速求 a 的 n 次幂」这类字样时，第一反应就该是倍增。

🎬 len = 13 的两种覆盖方案：为什么 ST 表只用两段

1目标区间长度 len = 13 = 1101₍₂₎ = 8 + 4 + 1

2方案一 · 二进制分解：取长度 8、4、1 的三段（互不重叠）→ 需要 2 次合并，且每次都要先知道「下一块取多长」——查询代价 O(log len)

3方案二 · 两段覆盖：k = lg[13] = 3，第一段 [l, l+8−1]（长 8），第二段 [r−8+1, r]（长 8）

4两段并集：8 + 8 = 16 > 13 → 重叠 3 个元素，但并集恰好盖住 [l, r]，一个不漏

5只需 1 次合并 → 与 len 无关的 O(1)。代价：重叠的 3 个元素被算了两次——对 max / min / gcd 无害，对求和致命

两方案的本质区别：二进制分解「不重叠但要拼很多块」；两段覆盖「只拼两块但允许重叠」。ST 表赌的是「你要求的运算不怕重复」——赌对了就有 O(1)。

③st 表的预处理：从一层「长」到下一层

定义：st[i][k] 表示从下标 i 开始、长度为 2^k 的区间 [i, i + 2^k − 1] 的答案。特别地，st[i][0] 就是「长度为 1 的区间」，也就是 a[i] 本身。

转移（倍增的灵魂）：一个长度为 2^k 的区间，一定可以从中间切成两个长度恰好为 2^k−1 的区间：

区间 [i, i + 2^k - 1]
   = [i, i + 2^(k-1) - 1]  ∪  [i + 2^(k-1), i + 2^k - 1]
      └── 左半段 ──┘            └── 右半段 ──┘
   左半段 = st[i][k-1]
   右半段 = st[i + 2^(k-1)][k-1]

所以：  st[i][k] = f( st[i][k-1] , st[i + 2^(k-1)][k-1] )

其中 f 是题目要求的运算（max / min / gcd / and / or …）。这个式子说明：每一层都可以由上一层「错位合并」得到——所有长度为 4 的区间答案由长度为 2 的拼出来，所有长度为 8 的由长度为 4 的拼出来，依此类推。

图 2：st 表就像一座「金字塔」，每层长度翻倍

递推的三个细节

层的编号从 0 开始：k = 0 是第一层（长度 1）。这样 2^k 与 k 的对应关系最自然。
右半段的起点：i + (1 << (k-1))。因为左半段占了 2^k−1 个位置。
循环顺序：外层 k、内层 i。必须先算完整个第 k−1 层，才能算第 k 层——因为第 k 层依赖同层的 k−1 数据。如果把 k 写成内层循环，就会读到还没算出来的值。

预处理复杂度：层数 K = ⌊log₂ n⌋ + 1，每层处理 n 个起点，总工作量 n × K ≈ n log n。

用格子图看一下 k = 1 这一层（每个格子表示「从这里开始、长度 2 的区间最大值」）：

把它和原始数组 9 3 1 7 5 6 0 8 对照：st[1][1] = max(9,3) = 9；st[2][1] = max(3,1) = 3；st[3][1] = max(1,7) = 7；st[4][1] = max(7,5) = 7；st[5][1] = max(5,6) = 6；st[6][1] = max(6,0) = 6；st[7][1] = max(0,8) = 8。注意这一层只有 7 个有效起点（8 − 2 + 1），最后一格越界不能用。

C++st 表的预处理（以区间最大值为例）

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int K = 17;                 // 2^17 = 131072 > 1e5，够用
int n, q, a[N];
int st[N][K + 1];                 // st[i][k]：从 i 开始、长度 2^k 的最大值
int lg[N];                        // lg[i] = 向下取整的 log2(i)

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // ---------- ① 预处理 log 表 O(n) ----------
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

    // ---------- ② 第 0 层：长度为 1 的区间 ----------
    for (int i = 1; i <= n; i++) st[i][0] = a[i];

    // ---------- ③ 逐层倍增：外层 k，内层 i ----------
    for (int k = 1; (1 << k) <= n; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
        }
    }
    return 0;
}

⚠️易错点：K 开小了导致越界

错误写法：n ≤ 10⁵，看到「10⁵ 大约是 2¹⁷」就写 st[N][17]，然后循环里访问 st[i][17]——数组越界（下标范围是 0~16）。

正确估算：需要的是「k 的最大值」，即满足 2^k ≤ n 的最大 k。对 n = 10⁵，2¹⁶ = 65536 ≤ 10⁵ < 2¹⁷，所以最大 k = 16，循环条件是 (1<<k) <= n，能到 k = 16。数组第二维要开 17 个元素（下标 0~16），即 st[N][17]。

更保险的写法：先算出 int K = lg[n] + 1;（即层数），然后数组用 vector<vector<int>> st(n+1, vector<int>(K+1));，或者直接按 const int K = 18; 留一个空位。经验值：n = 10⁵ 用 17，n = 10⁶ 用 21，n = 10⁷ 用 25。（因为 2¹⁷ = 131072 > 10⁵，2²¹ = 2097152 > 10⁶，2²⁵ = 33554432 > 10⁷。）

🎬 递推一列看看：st[3][·] 是怎么算出来的（数组 9 3 1 7 5 6 0 8）

1第 0 层：st[3][0] = a[3] = 1（长度 1 的区间 [3,3]，基础情形，直接抄）

2第 1 层：st[3][1] = max(st[3][0], st[3+2⁰][0]) = max(1, a[4]=7) = 7（区间 [3,4]）

3第 2 层：st[3][2] = max(st[3][1], st[3+2¹][1]) = max(st[3][1], st[5][1]) = max(7, 6) = 7（区间 [3,6] = {1,7,5,6}）

4第 3 层：st[3][3] 需要 st[3][2] 和 st[3+4=7][2]——但 st[7][2] 覆盖 [7,10]，越界（n=8），不存在。所以 st[3] 这一列到 k=2 为止

5观察：右半段的起点永远是 i + 2^k−1——「错位」恰好错开半个区间长，两半拼起来正好长 2^k

整张表就是 17 列这样的递推并行做：k=2 层五个值实测为 9 7 7 7 8（GCC 验证），与图 2 一致。易错提醒：每个起点的有效层数不同（i 越靠后能开的区间越短），由循环条件 i + (1<<k) − 1 ≤ n 自动控制。

🔍 代码逐段解析 · ST 表预处理（以区间最大值为例）

L3-7const int N = 100005, K = 17; 声明规模；st[N][K + 1] 第二维 K+1 = 18（下标 0~17）——易错：最大 k = 16（2¹⁶ ≤ 10⁵），从 0 编号所以需要 17 个元素，写 st[N][17] 恰好够但毫无余量，用 K+1 表意更清楚

L14-15① log 表：lg[1] = 0; for (i=2..n) lg[i] = lg[i >> 1] + 1; ——O(n) 纯整数递推，lg[i] 即 ⌊log₂ i⌋。查询时 lg[len] 要用多少次就预存多少，绝不能用 (int)log2(len) 现算

L18② 第 0 层：st[i][0] = a[i]——长度 1 的区间最值就是元素本身。这是基础情形，漏掉它整张表全是垃圾值

L21③ 外层循环 for (k = 1; (1 << k) <= n; k++)：层数上界由 2^k ≤ n 自动控制——n=8 时只到 k=3，绝不越界。易错：外层必须是 k（层在外、位置在内），写反了会读到还没算出来的第 k−1 层

L22内层循环 for (i = 1; i + (1 << k) - 1 <= n; i++)：起点 i 的合法条件是「区间右端点 i+2^k−1 不超过 n」——自动掐掉每层多出来的无效起点

L23转移：st[i][k] = max(st[i][k-1], st[i + (1 << (k-1))][k-1]); ——左半段从 i 起、右半段从 i + 2^k−1 起，两段各长 2^k−1，错位合并成完整区间

预处理总代价：层数 ⌊log₂n⌋+1 × 每层 O(n) = O(n log n)。注意这份代码只做了预处理，考试时还要接上查询部分（模块④）。

④O(1) 查询：两段覆盖的完整推导

查询 [l, r] 的三步：

设 len = r - l + 1                     ① 算出区间长度
设 k   = lg[len]                       ② 取「不超过 len 的最大 2 的幂」的指数
      （即 2^k ≤ len < 2^(k+1)）

答案 = f( st[l][k] , st[r - (1<<k) + 1][k] )     ③ 两段合并

  第一段：从 l 开始，长度 2^k  →  覆盖 [l, l + 2^k - 1]
  第二段：到 r 结束，长度 2^k  →  覆盖 [r - 2^k + 1, r]
  两段并集 = [l, r]（可能重叠）

为什么第二段的起点是 r - 2^k + 1？因为我们希望这一段正好以 r 结束。长度是 2^k，所以起点 = 终点 − 长度 + 1 = r - 2^k + 1。这个式子是整段代码里最容易写错的地方，务必理解而不是死记。

两段是否一定覆盖住 [l, r]？需要 l + 2^k − 1 ≥ r − 2^k，即 2^k+1 ≥ len + 1。由 2^k+1 > len 立得，恒成立。同时两段都在 [l, r] 内部（起点 ≥ l 因为 r − 2^k + 1 ≥ l，由 2^k ≤ len 保证）。所以「不漏」和「不多」都成立。

🎬 查询 [3, 7] 全程推演（数组 9 3 1 7 5 6 0 8，求区间最大值）

1确定查询区间：l = 3, r = 7。目标是 max{a[3], a[4], a[5], a[6], a[7]} = max{1, 7, 5, 6, 0}

2算出长度：len = r - l + 1 = 7 - 3 + 1 = 5

3取对数：k = lg[5] = 2（因为 2² = 4 ≤ 5 < 8 = 2³），于是 2^k = 4

4第一段：从 l = 3 开始，长度 4 → 覆盖 [3, 6]，答案 st[3][2] = max{1,7,5,6} = 7

5第二段：以 r = 7 结束，长度 4 → 起点 7 - 4 + 1 = 4，覆盖 [4, 7]，答案 st[4][2] = max{7,5,6,0} = 7

6观察覆盖：两段并集 = [3,6] ∪ [4,7] = [3,7]，完全覆盖目标区间；重叠部分是 [4,6]（3 个元素）

7合并：ans = max(7, 7) = 7。整个查询只用了 1 次 max 运算——与区间长度完全无关

8验证：暴力扫描 {1, 7, 5, 6, 0} 的最大值确实是 7，两者一致 ✓

注意第 6 步的重叠：[4, 6] 这三个元素被算了两遍。如果运算是「求和」，答案会变成 7 + 7 = 14 而不是真实的和 1+7+5+6+0 = 19……等等，这里 st 存的本来就是最大值而不是和，所以打这个比方只是为了强调「重叠」这件事对求和是致命的。对 max / min / gcd 这类可重复贡献的运算，重叠完全无害。

C++ST 表查询函数（区间最大值）

int query(int l, int r) {
    int len = r - l + 1;              // ① 长度
    int k = lg[len];                   // ② 取「不超过 len 的最大 2 的幂」的指数
    return max(st[l][k], st[r - (1 << k) + 1][k]);   // ③ 两段合并
}

// 如果不想预处理 lg 数组，可以直接用 GCC 内建函数：
// int k = __lg(len);      // 返回 floor(log2(len))，O(1) 且没有精度问题
// int k = 31 - __builtin_clz(len);   // 等价写法，clz = count leading zeros

运行结果

输入：8 8
      9 3 1 7 5 6 0 8
      1 6
      1 5
      2 7
      2 6
      1 8
      4 8
      3 7
      1 8
输出：9
      9
      7
      7
      9
      8
      7
      9

⚠️易错点：右段起点写成 r - (1<<k)

症状：查询结果偶尔偏小（求最大值时），而且往往是「区间右端那几个元素没被算进去」导致的。

原因：右段要「以 r 结尾」，起点必须是 r - 2^k + 1。
自己推一遍就不会忘：起点 + 长度 − 1 应该等于终点 r，即 起点 + 2^k − 1 = r，解出 起点 = r − 2^k + 1。
验证方法：用 l = r（长度 1，k = 0）代入：起点 = r − 1 + 1 = r，正好就是 st[r][0] = a[r]，正确。再用 len = 2（k = 1）验证：起点 = r − 2 + 1 = r − 1，覆盖 [r−1, r]，正确。凡是公式，都拿 l == r 和 len == 2 这两个边界试一遍。

🔍 代码逐段解析 · ST 表查询函数

第 1 行 int len = r - l + 1;：区间长度。闭区间 [l, r] 的元素个数 = 终点 − 起点 + 1，这个 +1 是「差一错误」高发点。

第 2 行 int k = lg[len];：查预处理的 log 表得到 ⌊log₂ len⌋。此时 2^k ≤ len < 2^k+1——「不超过 len 的最大 2 的幂」的指数。若用 GCC 内建可写 __lg(len)，O(1) 无精度问题。

第 3 行 return max(st[l][k], st[r - (1 << k) + 1][k]);：左段 st[l][k] 覆盖 [l, l+2^k−1]（贴住左端），右段 st[r−2^k+1][k] 覆盖 [r−2^k+1, r]（贴住右端）。易错 1：右段起点必须 +1——由「起点 + 2^k − 1 = r」反解而来，写掉 +1 右端就漏了元素；易错 2：两段必须用同一个 k——若左右两段取了不同的 k，覆盖性证明不再成立。

易错点 3（浮点取 k）：千万不要 int k = (int)log2(len);——浮点误差可能让 len=8 时算出 k=2，查询错一层且极难调试。用 lg 表或 __lg。

复杂度：三步全是 O(1)——2 次数组访问 + 1 次 max。与 len 完全无关，这就是 ST 表的核心卖点。

⑤log 表：也要 O(n) 预处理，才能 O(1) 查

问题：查询时需要 k = ⌊log₂ len⌋。如果每次都用 log2() 函数实时计算，会带来两个麻烦：浮点函数慢（常数大），且可能有精度误差（例如 log2(8) 算出 2.9999999 或 3.0000001，直接取整会得到 2 或 3，差一位就全错）。

解决方案：预先打一张 log 表。因为 ⌊log₂ i⌋ 只有 O(log n) 种取值，且可以直接用递推在 O(n) 内算完：

C++log 表的三种写法

// ---------- 写法 A：递推打表 O(n)，最推荐 ----------
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
// 原理：i / 2 把二进制右移一位，log2 恰好减 1
// 验证：lg[8] = lg[4] + 1 = (lg[2]+1) + 1 = ((lg[1]+1)+1) + 1 = 3 ✓

// ---------- 写法 B：GCC 内建函数 O(1)，最简单 ----------
int k = __lg(len);                    // 注意是 __lg 不是 log2

// ---------- 写法 C：浮点数 + 修正（不推荐，但要认识） ----------
int k = (int)(log2(len) + 1e-9);     // 加 1e-9 抵消向下误差

运行结果

i       : 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
lg[i]   : 0  1  1  2  2  2  2  3  3  3  3  3  3  3  3  4
2^lg[i] : 1  2  2  4  4  4  4  8  8  8  8  8  8  8  8 16
（2^lg[i] 就是「不超过 i 的最大 2 的幂」，这个值恰好等于区间第一段的长度）

💡 为什么推荐写法 A（递推打表）而不是写法 B（__lg）？

写法 A 的优点：① 完全可移植，不依赖编译器内建；② 逻辑透明，一眼看懂含义；③ 还可以顺手利用这张表做别的预处理。
写法 B 的优点：代码最短，省掉一行循环和 O(n) 的空间（虽然 lg 数组本身也就 n 个 int）。
写法 C 的风险：浮点精度问题在高强度数据下确实会翻车（尤其在 32 位环境下 log2 的实现精度不足），考场上不要用。

实用建议：平时用写法 A 稳妥，赶时间时用写法 B。如果读入的数据量特别大（比如 10⁷），写法 B 省下的那一点时间也挺可观。

🎬 递推 lg[13]：右移一位，对数减一

1目标：lg[13] = ⌊log₂ 13⌋。递推式：lg[i] = lg[i >> 1] + 1

2lg[13] = lg[13 >> 1] + 1 = lg[6] + 1（13 = 1101₍₂₎ 右移变 110₍₂₎）

3lg[6] = lg[3] + 1（110₍₂₎ 右移变 11₍₂₎）

4lg[3] = lg[1] + 1（11₍₂₎ 右移变 1₍₂₎）；lg[1] = 0（递推的种子）

5回代：lg[3] = 1，lg[6] = 2，lg[13] = 3。验证：2³ = 8 ≤ 13 < 16 = 2⁴ ✓

整个递推只用了「二进制右移一位 = 对数减一」这一条整数性质——全程没有浮点数，绝无精度误差。对照上面的运行结果表：lg[8]=3、lg[9..15]=3、lg[16]=4，每一个 2 的幂处恰好 +1。

⑥ST 表的边界与四个局限

局限 1 · 完全静态

数组一旦修改，几乎整张表都要重算（因为每个元素会出现在 O(log n) 个区间里）。题目里出现「单点修改」「区间加」「区间赋值」字样，就必须换线段树或树状数组。

局限 2 · 只支持「可重复贡献」

求最大值 ✓、最小值 ✓、gcd ✓、lcm ✓、按位与 ✓、按位或 ✓；求和 ✗、异或 ✗、计数 ✗（重叠会重复计算）。用错运算的后果是「答案偏大且看不出来哪里错」，非常隐蔽。

局限 3 · 空间 O(n log n)

n = 10⁵ 时约 7 MB（安全）；n = 10⁶ 时约 80 MB（要小心）；n = 10⁷ 时约 800 MB（必爆）。看到大 n 先算内存：n × (⌊log₂ n⌋ + 1) × sizeof(int)。

局限 4 · 不好求「最值的位置」

如果题目要输出「最大值第一次出现在下标几」，直接存值的 ST 表做不到。解法是让 st 存下标：比较时用 a[st[...]] 的值来比大小，但表中保存的是下标。这样既能取到值、也能取到位置。

「存下标」的写法示例（求区间最大值的第一处位置）：

// st[i][k] 存的是「答案所在的下标」，而不是答案本身
int better(int x, int y) {            // 返回二者中「更优」的下标
    return a[x] >= a[y] ? x : y;         // 用 >= 取最左；用 > 取最右
}

// 预处理
for (int i = 1; i <= n; i++) st[i][0] = i;
for (int k = 1; (1 << k) <= n; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++)
        st[i][k] = better(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);

// 查询：返回最大值的「最左位置」
int queryPos(int l, int r) {
    int k = lg[r - l + 1];
    return better(st[l][k], st[r - (1 << k) + 1][k]);
}

⚠️ 取「最左」还是「最右」需要想清楚：用 a[x] >= a[y] ? x : y 时，若两段的值相等，会返回左边那一段的位置，而左边那一段的下标又更小，所以整体得到的是「最左」的最值位置。如果题目要「最右」，把 >= 改成 > 即可。这个符号的选择会直接影响答案，写之前先想清楚题目要的是哪一个。

🎬 「存下标」版查询推演：数组 3 9 2 9 5，问 [1,4] 最大值在最左哪里

1表中存的是下标：st[i][0] = i。第 1 层：st[1][1] = better(1, 2)——a[1]=3 < a[2]=9 → 2；st[3][1] = better(3, 4)——a[3]=2 < a[4]=9 → 4

2第 2 层：st[1][2] = better(st[1][1], st[3][1]) = better(2, 4)——a[2]=9 与 a[4]=9 相等！走「相等」分支

3return min(x, y) = min(2, 4) = 2 → st[1][2] = 2（[1,4] 的最大值 9 首次出现在下标 2）

4查询 [1,4]：len = 4, k = 2；右段起点 = 4 − 4 + 1 = 1，两段恰好重合 → 答案 = better(st[1][2], st[1][2]) = 2 ✓

5查询 [2,5]：len = 4, k = 2；st[2][2] = better(st[2][1], st[4][1]) = better(2, 4) = 2；右段起点 = 5 − 4 + 1 = 2 → 答案 2 ✓（最大值 9 只在下标 2、4，最左是 2）

第 2~3 步是「存下标」版的灵魂：值相等时取更小的下标，才能保证「最左」。若写成 max(x, y)，同一组数据会输出 4（最右）——差一个函数，答案完全不同。

🔍 代码逐段解析 · 存下标的 ST 表

better(x, y) 函数：return a[x] >= a[y] ? x : y; ——比较的是 a[ ] 里的值，返回的是下标。>= 让「值相等时保留左边的 x」→ 全局得到最左位置；改成 > 就变成最右。易错：若写成 return a[x] >= a[y] ? x : y; 却在合并时把左右段顺序颠倒（先右后左），「相等取左」就失效了——比较函数与合并顺序必须配套。

预处理（三处变化）：① st[i][0] = i;（长度 1 的区间「最值位置」就是 i 自己，不是 a[i]！）；② 合并语句 st[i][k] = better(st[i][k-1], st[i + (1<<(k-1))][k-1]);——框架与存值版完全相同，只是 max 换成了 better；③ 循环条件不变。

查询 queryPos(l, r)：与存值版唯一的区别是返回值——return better(st[l][k], st[r - (1 << k) + 1][k]); 返回下标。要拿值再 a[p] 一下即可。易错：「最大值的位置」和「最大值本身」别搞混，输出前想清楚题目要哪个。

复杂度：与存值版完全相同——预处理 O(n log n)、查询 O(1)。代价为零，能力 +1，是「求位置」类问题的标准起手式（拓展 1 的超级钢琴、实践 A1 都靠它）。

⑦五大结构选型对比：什么时候该用 ST 表

我们已经学过（或即将学）好几种「区间查询」的结构，它们的能力边界完全不同。这张表值得抄到笔记本首页：

结构	能否修改	支持的运算	预处理	单次查询	空间
ST 表	不能	可重复贡献 max / min / gcd / and / or	O(n log n)	O(1)	O(n log n)
前缀和	不能	只有可减运算（+，xor）	O(n)	O(1)	O(n)
树状数组	单点修改	可减运算优先（+，xor）	O(n)	O(log n)	O(n)
线段树	单点 / 区间修改	几乎所有可结合运算	O(n)	O(log n)	O(n)
单调队列	—	滑动窗口最值	—	均摊 O(1)	O(k)

✅ 该用 ST 表

特征：数据完全静态，查询次数很多（q 与 n 同阶或更大），只要求 max / min / gcd / and / or。

例子：「n 天历史气温的区间最高值」「区间 gcd」「子矩阵最大值」。

❌ 不该用 ST 表

特征 1：有修改操作 → 用线段树 / 树状数组。
特征 2：运算不可重复贡献（求和、异或）→ 用前缀和 / 树状数组 / 线段树。
特征 3：是「滑动窗口」而非任意区间 → 用单调队列（空间只要 O(k)）。
特征 4：n 达到 10⁷ 且内存只有 256 MB → 用分块或单调队列。

💡 「静态 + 大量查询」为什么这么特殊？

因为「静态」意味着我们可以在读入之后、查询之前花任意多的时间做预处理——预处理再贵也只是一次性的。而「大量查询」意味着单次查询的代价会被放大 q 倍，所以值得用 O(n log n) 的预处理去换 O(1) 的查询。

量化一下：假设 n = q = 10⁵。

· 用暴力：10⁵ × 平均区间长度 ≈ 10⁹ 次操作 → 超时。
· 用线段树：10⁵ × log(10⁵) ≈ 1.7×10⁶ 次操作 → 能过，但还有优化空间。
· 用 ST 表：10⁵ × 17（预处理）+ 10⁵ × 1（查询）≈ 1.8×10⁶ 次操作 → 与线段树同量级，但查询部分是纯 O(1)，常数小得多。

真正拉开差距的场景：当 q = 10⁷ 时，线段树需要 1.7×10⁸ 次操作（危险），而 ST 表只需要 10⁷ 次（轻松）。查询越多，ST 表的优势越明显。

🎬 三道题放面前，选哪个结构？

题 1「n 天历史气温（永不修改），q = 10⁶ 次问任意区间的最高温」→ ST 表。静态 + 可重复贡献 + 查询多，三条全中

题 2「股票价格实时更新，随时问最近 k 天的最高价」→ 单调队列。窗口定长滑动，数据流式——用 ST 表既费空间又跑不满

题 3「任务不断入队出队，随时问当前优先级最高的」→ 堆（priority_queue）。集合动态增删，没有「区间」的概念

题 4「静态数组，q 次问区间和」→ 前缀和，不是 ST 表！求和不幂等（重叠会重复计数），而且前缀和预处理只要 O(n)

题 5「静态数组，q 次问区间 gcd」→ ST 表。gcd(x,x)=x 幂等 ✓，静态 ✓，查询多 ✓

决策三问：①数据会变吗？②运算幂等吗？③是定长窗口还是任意区间？三问答完，结构自然浮出水面——「窗口滑动 → 单调队列；动态增删 → 堆；任意静态区间 → ST 表；可减运算 → 前缀和」。

⑧二维 ST 表：把倍增用到两个方向

问题：给定 n×m 的矩阵，多次询问「以 (x1, y1) 为左上角、(x2, y2) 为右下角的子矩阵中的最大值」。

定义：st[i][j][kx][ky] 表示「以 (i, j) 为左上角、高度 2^kx、宽度 2^ky」的矩形区域内的答案。四个维度：行起点、列起点、行方向的倍增层、列方向的倍增层。

转移：一个大矩形可以「先横切再竖切」切成四个小矩形，所以递推也是三维加一维：

st[i][j][kx][ky]
  = f( st[i][j][kx-1][ky-1] ,  st[i + 2^(kx-1)][j][kx-1][ky-1] ,
       st[i][j + 2^(ky-1)][kx-1][ky-1] ,  st[i + 2^(kx-1)][j + 2^(ky-1)][kx-1][ky-1] )

查询：与一维完全同理，用 4 个子矩形覆盖目标矩形（四角各放一块），允许重叠：

h = x2 - x1 + 1,  w = y2 - y1 + 1
kx = lg[h],       ky = lg[w]
ans = f( st[x1][y1][kx][ky] ,
         st[x2 - (1<<kx) + 1][y1][kx][ky] ,
         st[x1][y2 - (1<<ky) + 1][kx][ky] ,
         st[x2 - (1<<kx) + 1][y2 - (1<<ky) + 1][kx][ky] )

图 3：二维查询用四个 2^kx×2^ky 的矩形覆盖

空间账：二维 ST 表的代价

总空间 = n × m × (⌊log₂ n⌋+1) × (⌊log₂ m⌋+1) × 4 字节。

n = m = 300：300×300×9×9 ≈ 7.3×10⁶ 个 int ≈ 29 MB → 安全。
n = m = 1000：1000×1000×10×10 ≈ 10⁸ 个 int ≈ 400 MB → 必爆。

结论：二维 ST 表只适合「边长在几百以内」的小规模矩阵。对于边长达 1000 以上的「求 n×n 子矩阵极差最小」这类题（如 P2216 理想的正方形），应该改用「两次一维滑动窗口（单调队列）」——那是 O(nm) 时间、O(nm) 空间的解法（见上一讲的案例4）。

C++二维 ST 表求子矩阵最大值（n, m ≤ 300）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305, MAXK = 10;
int n, m, q;
int st[MAXN][MAXN][MAXK][MAXK];
int lg[MAXN];

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= max(n, m); i++) lg[i] = i == 1 ? 0 : lg[i >> 1] + 1;

    // 第 0 层：单个格子
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &st[i][j][0][0]);

    // 先只在行方向倍增（ky = 0）
    for (int kx = 1; (1 << kx) <= n; kx++)
        for (int i = 1; i + (1 << kx) - 1 <= n; i++)
            for (int j = 1; j <= m; j++)
                st[i][j][kx][0] = max(st[i][j][kx-1][0],
                                        st[i + (1 << (kx-1))][j][kx-1][0]);

    // 再在列方向倍增（复用上面算好的结果）
    for (int kx = 0; (1 << kx) <= n; kx++)
        for (int ky = 1; (1 << ky) <= m; ky++)
            for (int i = 1; i + (1 << kx) - 1 <= n; i++)
                for (int j = 1; j + (1 << ky) - 1 <= m; j++)
                    st[i][j][kx][ky] = max(st[i][j][kx][ky-1],
                                          st[i][j + (1 << (ky-1))][kx][ky-1]);

    while (q--) {
        int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int kx = lg[x2 - x1 + 1], ky = lg[y2 - y1 + 1];
        int ans = max(max(st[x1][y1][kx][ky],
                           st[x2 - (1 << kx) + 1][y1][kx][ky]),
                       max(st[x1][y2 - (1 << ky) + 1][kx][ky],
                           st[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky]));
        printf("%d\n", ans);
    }
    return 0;
}

🔍 为什么「先横向倍增、再纵向倍增」可以分两轮做？

因为两个方向的倍增是相互独立的：第一轮把「高度为 2^kx、宽度为 1」的所有竖条算完；第二轮在这个基础上把宽度也扩展成 2^ky。「先扩展行、再扩展列」和「先扩展列、再扩展行」结果相同——因为 max 满足结合律与交换律。分两轮写比写四重嵌套的循环更清晰，也不容易搞错下标。

🎬 二维查询四角覆盖：矩阵 3×4（1 2 5 6 / 8 7 6 5 / 8 5 5 5），查询 [1,1]–[3,4]

1目标矩形：行 [1,3]、列 [1,4]。h = 3，w = 4

2取对数：kx = lg[3] = 1（2¹=2 ≤ 3），ky = lg[4] = 2（2²=4 ≤ 4）。每块覆盖矩形 = 2×4

3① 左上：st[1][1][1][2] = 行 [1,2] × 列 [1,4] 的最大值 = max{1,2,5,6,8,7,6,5} = 8

4② 左下：起点 = x2 − 2^kx + 1 = 3 − 2 + 1 = 2 → st[2][1][1][2] = 行 [2,3] × 列 [1,4] = max{8,7,6,5,8,5,5,5} = 8

5③ 右上：列起点 = y2 − 4 + 1 = 1 → 与 ① 相同 = 8；④ 右下：st[2][1][1][2] 与 ② 相同 = 8（本例宽恰好 4=2²，列方向两块重合）

6合并：max(8, 8, 8, 8) = 8 ✓（全矩阵最大值确实是 8，GCC 实测一致）。行方向两块 [1,2] 与 [2,3] 重叠了第 2 行——对 max 无害

一维是「两段覆盖」，二维就是「四角覆盖」：行方向 × 列方向各取两段，组合成 2×2 = 4 块。查询代价 = 4 次取表 + 3 次合并，仍是 O(1)。

🔍 代码逐段解析 · 二维 ST 表（n, m ≤ 300）

声明 int st[MAXN][MAXN][MAXK][MAXK]：四维分别是行起点 i、列起点 j、行的倍增层 kx、列的倍增层 ky。MAXN=305, MAXK=10（2⁹=512 > 300，最大层 8~9，开 10 留余量）。易错 1：这个数组约 305×305×10×10×4B ≈ 37 MB，全局声明（放堆/静态区）没问题，放进 main 里当局部变量就是栈溢出。

第 0 层读入：scanf("%d", &st[i][j][0][0]) ——直接把矩阵元素读进第 0 层，连 a 数组都省了。

第一轮（行方向，ky=0）三重循环：外层 kx、中层 i（起点）、内层 j。转移 st[i][j][kx][0] = max(st[i][j][kx-1][0], st[i + (1<<(kx-1))][j][kx-1][0]) ——把「高度 2^kx×宽 1」的竖条切成上下两半。做完后每个 (i,j) 存着「以它为左上角、高 2^kx、宽 1」竖条的最大值。

第二轮（列方向）四重循环：注意 kx 从 0 开始（把 kx=0 的单行情况也补上），ky 从 1 开始。转移 st[i][j][kx][ky] = max(st[i][j][kx][ky-1], st[i][j + (1<<(ky-1))][kx][ky-1]) ——把两个「宽 2^ky−1」的竖条横着拼起来。易错 2：第二轮外层是 kx 不是 ky——「先保证行方向全算完，再逐层扩展列」，两轮的循环变量顺序不能乱。

查询：kx = lg[x2-x1+1], ky = lg[y2-y1+1]，四个角分别是 st[x1][y1]、st[x2-dx+1][y1]、st[x1][y2-dy+1]、st[x2-dx+1][y2-dy+1]（dx=2^kx，dy=2^ky）。易错 3：四个角的行列起点都要「+1 修正」，与一维右端点完全同理——行贴 x2、列贴 y2。

验证：样例 3×4 矩阵三组查询输出 8 8 6（GCC 实测一致）。

案例案例1：ST 表模板（P3865 【模板】ST 表 & RMQ 问题）洛谷真题

题目：给定 n 个数和 m 次询问，每次询问 [l, r] 内的最大值。n ≤ 10⁵，m ≤ 2×10⁶。

为什么这题必须用 ST 表：注意询问次数 m 高达 2×10⁶。用线段树（O(log n) 一次）总操作约 2×10⁶ × 17 = 3.4×10⁷，虽然能过但压力不小；而 ST 表每次查询只需 2 次取表 + 1 次 max，总操作量约 6×10⁶——这就是 O(1) 查询的威力。

C++P3865 完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, K = 17;
int n, m, a[N], st[N][K + 1], lg[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // ① log 表
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

    // ② 第 0 层
    for (int i = 1; i <= n; i++) st[i][0] = a[i];

    // ③ 倍增预处理
    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);

    while (m--) {
        int l, r; scanf("%d%d", &l, &r);
        int k = lg[r - l + 1];
        printf("%d\n", max(st[l][k], st[r - (1 << k) + 1][k]));
    }
    return 0;
}

运行结果

输入：8 8
      9 3 1 7 5 6 0 8
      1 6
      1 5
      2 7
      2 6
      1 8
      4 8
      3 7
      1 8
输出：9 9 7 7 9 8 7 9（每行一个）

⚠️易错点：用 cin / cout 会超时

症状：算法完全正确，但提交后 TLE（超时），尤其是 m = 2×10⁶ 这种大数据。

原因：cin/cout 默认与 C 的 stdio 同步（sync_with_stdio(true)），并且 endl 会强制刷新缓冲区，读写 2×10⁶ 组数据的开销可能达到 scanf/printf 的 3~5 倍。
两种解决方案：
① 改用 scanf / printf（本讲全部代码都采用这种方式）。
② 保留 cin/cout，但在 main 开头加两行：ios::sync_with_stdio(false); cin.tie(0);，并且不要用 endl，改用 '\n'。加速后基本能追上 scanf。
注意：一旦用了 sync_with_stdio(false)，就不能混用 cin 和 scanf——两者的缓冲区不同步，会读到错误数据。

🔍 代码逐段解析 · P3865 ST 表模板题

L3-4const int N = 100005, K = 17; 声明 st[N][K+1]——第二维 18 个元素（下标 0~17），覆盖最大层 k=16 并留余量

L7-9读入：注意用 scanf——m 高达 2×10⁶，cin 不关同步大概率 TLE（见上方易错点）

L11-12① log 表：lg[i] = lg[i >> 1] + 1 O(n) 递推。查询里每次都要查 lg[len]，这张表是 O(1) 查询的一部分，必须先打好

L14-16②③ 预处理：第 0 层抄入 a，再「层在外、位置在内」倍增到 k=16。n=10⁵ 时总操作 ≈ 1.7×10⁶，一眨眼完成

L18-20查询主循环：int k = lg[r - l + 1]; printf("%d\n", max(st[l][k], st[r - (1 << k) + 1][k])); ——两行完成一次查询。易错：每行末尾是 '\n'（printf 天然如此）；若用 cout 别写 endl

复杂度预处理 O(n log n) + 查询 O(m)。总操作 ≈ 1.7×10⁶ + 6×10⁶ ≈ 8×10⁶，对比线段树 ≈ 3.4×10⁷——这就是模板题选 ST 表的原因

样例 8 8 / 9 3 1 7 5 6 0 8 八组查询输出 9 9 7 7 9 8 7 9（GCC 实测一致）。这道题的全部考点：①模板默写正确；②读入方式扛得住 2×10⁶ 组询问。

案例案例2：平衡阵容（P2880 Balanced Lineup G）洛谷真题

题目：有 n 头奶牛排成一列，第 i 头的身高是 a[i]。给出 q 次询问，每次问 [l, r] 区间内「最高身高与最矮身高之差」。n ≤ 5×10⁴，q ≤ 2×10⁵。

做法：开两张 ST 表——一张求区间最大值（记为 stMax），一张求区间最小值（记为 stMin），预处理和查询各跑一遍，最后作差。

C++P2880 完整代码（双 ST 表）

#include <bits/stdc++.h>
using namespace std;
const int N = 50005, K = 16;
int n, q, a[N];
int stMax[N][K + 1], stMin[N][K + 1], lg[N];

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

    for (int i = 1; i <= n; i++) stMax[i][0] = stMin[i][0] = a[i];

    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            stMax[i][k] = max(stMax[i][k-1], stMax[i + (1 << (k-1))][k-1]);
            stMin[i][k] = min(stMin[i][k-1], stMin[i + (1 << (k-1))][k-1]);
        }

    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        int k = lg[r - l + 1];
        int mx = max(stMax[l][k], stMax[r - (1 << k) + 1][k]);
        int mn = min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
        printf("%d\n", mx - mn);
    }
    return 0;
}

运行结果

输入：6 3
      1 7 3 4 2 5
      1 5
      4 6
      2 2
输出：6
      3
      0
（[1,5] 内 max=7、min=1，差 6；[4,6] 内 max=5、min=2，差 3；
  [2,2] 只有一个元素，差 0）

💡 为什么不用「区间和」类的结构来做差值？

因为「最大值」和「最小值」是两个独立的、各自可重复贡献的运算，必须分别维护。不能像求和那样「用前缀和作差」——max[l..r] 无法通过 preMax[r] - preMax[l-1] 得到（前缀最值不具有可减性）。

一个可以省一半的优化：其实只需要「最大值 − 最小值」，所以可以把两张表合并成一张、每个位置存一个 pair<int,int>（max 与 min），然后合并时对 first 取 max、对 second 取 min。这样数组访问次数减少，但总空间不变。写成两张表更直观，推荐初学阶段用两张表。

🔍 代码逐段解析 · P2880 双 ST 表求区间极差

L3-4const int N = 50005, K = 16; n ≤ 5×10⁴：2¹⁵=32768 ≤ 50000 < 2¹⁶，最大层 k=15，第二维 17 个元素（K+1）足够

L6int stMax[N][K+1], stMin[N][K+1] 两张表并列声明——内存翻倍（2×50005×17×4B ≈ 6.8 MB），本题 n 小所以无压力；n 大时参见实践 A3 的内存账

L10第 0 层一行初始化两张表：stMax[i][0] = stMin[i][0] = a[i]; ——连续赋值从右往左，两个表都拿到 a[i]

L12-16预处理循环合二为一：同一个 (k, i) 下标同时更新两张表——stMax 用 max、stMin 用 min。易错：别把两张表的转移写串了（比如 stMax 里用了 min）——编译不报错、答案默默错

L18-23查询：同一个 k、同一对「两段起点」分别查两张表——mx = max(stMax[l][k], stMax[r-(1<<k)+1][k])，mn = min(...)，然后 printf("%d\n", mx - mn);。易错：mx 用 max 合并、mn 用 min 合并，方向别反

复杂度预处理 O(n log n)（两表并行，常数 ×2），查询 O(q)。极差 = mx − mn 在查询时现算，不需要第三张表——「极差」本身不可重复贡献，但它可以由两个可重复贡献的量组合而来

样例 6 3 / 1 7 3 4 2 5 三组查询输出 6 3 0（GCC 实测一致）。本题的思维点：「极差」不能直接做 ST 表，但拆成 max、min 两个子问题后各自都能做——把不可解的问题拆成可解的子问题，是设计算法的常用手法。

案例案例3：区间 GCD（可重复贡献的深度应用）洛谷真题

题目：给定 n 个数，q 次询问 [l, r] 内所有数的最大公约数。n ≤ 10⁵。

为什么 gcd 可以套 ST 表？逐个验证可重复贡献的两个条件：

交换律

gcd(x, y) = gcd(y, x) ✓（两个数的公约数与顺序无关）

结合律

gcd(gcd(x,y), z) = gcd(x, gcd(y,z)) ✓（都等于三者的最大公约数）

幂等性（关键）

gcd(x, x) = x ✓ ——这就是「重叠」不会影响答案的原因。x 与自身取 gcd 还是 x，所以同一个元素算两遍完全无害。

反例 · 求和

sum(x, x) = 2x ≠ x ✗ ——幂等性不成立，所以重叠会让求和结果重复计元素。

C++区间 GCD 的 ST 表实现

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, K = 17;
int n, q, a[N], st[N][K + 1], lg[N];

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

    for (int i = 1; i <= n; i++) st[i][0] = a[i];

    // 唯一的变化：把 max 换成 __gcd
    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            st[i][k] = __gcd(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);

    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        int k = lg[r - l + 1];
        printf("%d\n", __gcd(st[l][k], st[r - (1 << k) + 1][k]));
    }
    return 0;
}

运行结果

输入：6 3
      12 8 6 15 20 9
      2 5
      1 6
      3 3
输出：1
      1
      6
（[2,5] 内 {8,6,15,20} 的 gcd = 1；[1,6] 全体的 gcd = 1；
  [3,3] 只有 6，gcd = 6）

🔍 这道题揭示了 ST 表的「通用模板」本质

把三道题的代码摆在一起对比：P3865（区间最大值）、P2880（区间极差）、区间 GCD——它们的代码几乎一模一样，唯一区别就是合并时用的函数：

· 区间最大值：merge = max
· 区间极差：merge = pair(max, min)，需要两个分量
· 区间 GCD：merge = __gcd
· 区间按位与：merge = &
· 区间按位或：merge = |

结论：ST 表是一个「模板化」的结构——只要运算满足「可重复贡献」，把 max 替换成目标函数就能直接用。考试时不必重新推导，只需判断两件事：①数据是否静态；②运算是否可重复贡献。两个都是「是」，就放心套模板。

⚠️易错点：区间异或（xor）不能用 ST 表

常见的误判：觉得「异或也是按位运算，和按位与差不多」，就直接套了 ST 表。结果答案偏大——因为异或不满足幂等性：x ^ x = 0 ≠ x。重叠部分被异或了两次，直接抵消成了 0。

正确的判断方法：逐一代入检查 f(x, x) == x 是否成立。
· max(x, x) = x ✓ 可用
· min(x, x) = x ✓ 可用
· gcd(x, x) = x ✓ 可用
· x & x = x ✓ 可用
· x | x = x ✓ 可用
· x + x = 2x ✗ 不可用
· x ^ x = 0 ✗ 不可用
区间异或的正确做法：用前缀异或（preXor[r] ^ preXor[l-1]），O(1) 查询、O(n) 预处理，比 ST 表还简单——因为异或满足「可减性」（x ^ x = 0 恰好让它可逆）。

🔍 代码逐段解析 · 区间 GCD 的 ST 表

与 P3865 的 diff 只有 2 处：① 预处理转移 st[i][k] = __gcd(st[i][k-1], st[i + (1<<(k-1))][k-1]);——max 换成 __gcd（GCC 内建，在 <algorithm> / bits 里；两个参数须同类型）；② 查询 printf("%d\n", __gcd(st[l][k], st[r-(1<<k)+1][k]));。其余逐行相同——这正是「模板化」的体现。

易错 1：__gcd 遇到 0 的行为：gcd(0, x) = x。若题目数据可能含 0，表和查询都能正常工作（gcd 的幺元是 0），但要想清楚题意。

易错 2：若值域达 10¹⁸，把 int st[N][K] 换成 long long——内存翻倍（n log n × 8B），n = 10⁵ 时约 14 MB 尚可，但必须先算内存账（见实践 A3 的公式）。

验证：输入 6 3 / 12 8 6 15 20 9，三组查询输出 1 1 6：gcd{8,6,15,20}=1（8 与 6 的 gcd=2，再与 15 的 gcd=1，gcd 一旦变 1 就永远是 1）；gcd 全体=1；单元素 6 的 gcd=6。GCC 实测一致。

一个有趣的观察：gcd-ST 表还有个经典副产品——「区间 gcd ≤ 区间 min」且「若区间 min 恰好整除区间 gcd，可以快速判断某段是否全部相等」等技巧，在一些进阶题（线段树 GCD 维护）里会重逢。

案例案例4：二维 ST 表求子矩阵最大值综合应用

题目：给定 n×m 的矩阵（n, m ≤ 300）和 q 次询问，每次给出 (x1, y1, x2, y2)，求该子矩阵内的最大值。

为什么这题尺寸要限制在 300：因为二维 ST 表的空间是 O(nm log n log m)。n = m = 300 时约 7.3×10⁶ 个 int（29 MB），安全；n = m = 1000 时约 10⁸ 个 int（400 MB），会爆内存。这是 ST 表「用空间换时间」最直接的代价体现。

构建思路回顾：分两轮倍增——先只在行方向倍增（每个位置存「高度 2^kx、宽度 1」的竖条最大值），再在列方向倍增。

C++二维 ST 表完整实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305, MAXK = 10;
int n, m, q;
int st[MAXN][MAXN][MAXK][MAXK];
int lg[MAXN];

int main() {
    scanf("%d%d%d", &n, &m, &q);

    lg[1] = 0;
    for (int i = 2; i <= max(n, m); i++) lg[i] = lg[i >> 1] + 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &st[i][j][0][0]);

    // 第一轮：行方向倍增（ky = 0）
    for (int kx = 1; (1 << kx) <= n; kx++)
        for (int i = 1; i + (1 << kx) - 1 <= n; i++)
            for (int j = 1; j <= m; j++)
                st[i][j][kx][0] = max(st[i][j][kx-1][0],
                                        st[i + (1 << (kx-1))][j][kx-1][0]);

    // 第二轮：列方向倍增（复用第一轮的结果）
    for (int kx = 0; (1 << kx) <= n; kx++)
        for (int ky = 1; (1 << ky) <= m; ky++)
            for (int i = 1; i + (1 << kx) - 1 <= n; i++)
                for (int j = 1; j + (1 << ky) - 1 <= m; j++)
                    st[i][j][kx][ky] = max(st[i][j][kx][ky-1],
                                          st[i][j + (1 << (ky-1))][kx][ky-1]);

    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

        int kx = lg[x2 - x1 + 1], ky = lg[y2 - y1 + 1];
        int dx = (1 << kx), dy = (1 << ky);

        int a1 = st[x1][y1][kx][ky];                        // 左上
        int a2 = st[x2 - dx + 1][y1][kx][ky];              // 左下
        int a3 = st[x1][y2 - dy + 1][kx][ky];              // 右上
        int a4 = st[x2 - dx + 1][y2 - dy + 1][kx][ky];    // 右下

        printf("%d\n", max(max(a1, a2), max(a3, a4)));
    }
    return 0;
}

运行结果

输入：3 4 3
      1 2 5 6
      8 7 6 5
      8 5 5 5
      1 1 2 2
      1 1 3 4
      2 3 3 4
输出：8
      8
      6
（[1,1]-[2,2] 子矩阵 {1,2,8,7} 最大 8；
  [1,1]-[3,4] 全矩阵最大 8；
  [2,3]-[3,4] 子矩阵 {6,5,5,5} 最大 6）

💡 二维 ST 表 vs 两次单调队列：如何选择？

两次单调队列（上一讲案例4）：时间 O(nm)、空间 O(nm)，代码稍长（要写 4 遍滑动窗口）。二维 ST 表：预处理 O(nm log n log m)、查询 O(1)、空间 O(nm log n log m)。

选择原则：
① 如果只需要求几个固定大小的方阵（如 n×n 的理想正方形）→ 两次单调队列更优（空间小、常数小）。
② 如果矩阵小（边长 ≤ 300）、但询问次数极多、且询问的矩形尺寸各不相同 → 二维 ST 表更优（O(1) 查询，尺寸任意）。
③ 如果矩阵很大（边长 ≥ 1000）→ 只能用单调队列，二维 ST 表空间会爆。

核心权衡：「空间换时间」的收益必须大于代价。当空间已经吃紧时，就该放弃 ST 表去换一个空间更省的算法。

🔍 代码逐段解析 · 二维 ST 表完整实现

本代码与模块⑧的版本同构（那里已逐段解析过），这里只补三点考场实操细节：

① 查询用临时变量 a1~a4：int a1 = st[x1][y1][kx][ky]; int a2 = st[x2 - dx + 1][y1][kx][ky]; ... 先把四个角存成命名变量再 max(max(a1,a2), max(a3,a4))——比一行嵌套四个下标表达式可读性好得多，也更容易检查每个「+1 修正」是否写对。注释里标清「左上/左下/右上/右下」是很好的习惯。

② 行列别搞混：行方向用 dx = 1 << kx 修正第一维下标，列方向用 dy = 1 << ky 修正第二维——易错：把 dy 用到行上、dx 用到列上（题目 n≠m 时必错，n=m 时可能侥幸全对，极隐蔽）。写完拿 n≠m 的数据测一遍。

③ 空间声明：st[305][305][10][10] ≈ 37 MB，必须全局声明。若题目内存卡 64 MB，还要扣掉其他数组——先算账再动手（实践 A3 的五步流程）。

验证：样例 3×4 矩阵三组查询输出 8 8 6（GCC 实测一致，推演见上方动画）。

模块 03

实践应用

三道递进的编程题：从「取最值的位置」，到「换个运算」，再到「算清内存预算」。

A基础模板普及/提高-

给定 n 个数和 q 次询问，每次询问 [l, r] 内最大值第一次出现的下标（若有多个相同最大值，取最左的那个）。n ≤ 10⁵。

查看参考答案

关键转变：让 ST 表存「下标」而不是「值」。比较时通过 a[] 取值来比大小，但表里保存的是位置。

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, K = 17;
int n, q, a[N];
int st[N][K + 1];                 // 存「下标」
int lg[N];

// 返回更优（值更大）的下标；值相等时返回更小的下标 → 保证「最左」
int better(int x, int y) {
    if (a[x] != a[y]) return a[x] > a[y] ? x : y;
    return min(x, y);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

    for (int i = 1; i <= n; i++) st[i][0] = i;

    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            st[i][k] = better(st[i][k-1], st[i + (1 << (k-1))][k-1]);

    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        int k = lg[r - l + 1];
        int p = better(st[l][k], st[r - (1 << k) + 1][k]);
        printf("%d\n", p);
    }
    return 0;
}

验证：数组 3 9 2 9 5，询问 [1,4] → 最大值是 9，第一次出现在下标 2 → 输出 2。询问 [2,5] → 最大值 9 在下标 2 → 输出 2。

为什么「相等时取 min(x,y)」能保证最左？两段中，左段 st[l][k] 覆盖的是 [l, l+2^k-1]，右段覆盖 [r-2^k+1, r]，左段的所有下标都 ≤ 右段。所以当两段的值相等时，取下标更小的那个就是整个区间里最左的出现位置。
若要「最右」：把 min(x, y) 改成 max(x, y) 即可。

逐段解析：① better(x, y)：先比值 a[x] > a[y] ? x : y，值相等走 return min(x, y)——两行分工明确：「大者胜，平局取小下标」。注意第一行用 != 分流而不是直接 >=，逻辑更清晰且天然兼容「最左」语义；② st[i][0] = i; ——第 0 层存下标而不是 a[i]，这是本题与存值版的分水岭，写错成 = a[i] 后面全乱；③ 预处理转移 st[i][k] = better(st[i][k-1], st[i + (1<<(k-1))][k-1]); ——框架与模板一字不差，只是比较器换了；④ 查询 int p = better(st[l][k], st[r - (1 << k) + 1][k]); 输出 p。易错：左段 st[l][k] 必须是 better 的第一个参数——「平局取 min」依赖「左段下标 ≤ 右段下标」这一事实，参数顺序颠倒后平局逻辑失效。

B换运算普及+/提高

给定 n 个数，q 次询问 [l, r] 内所有数的按位与（AND）。n, q ≤ 10⁵。

查看参考答案

第一步（必做）：判断按位与是否可重复贡献。

· 交换律：x & y = y & x ✓
· 结合律：(x & y) & z = x & (y & z) ✓
· 幂等性：x & x = x ✓ —— 三个条件都满足，可以用 ST 表。

// 预处理：把 max 换成 &
for (int i = 1; i <= n; i++) st[i][0] = a[i];
for (int k = 1; (1 << k) <= n; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++)
        st[i][k] = st[i][k-1] & st[i + (1 << (k-1))][k-1];

// 查询：把 max 换成 &
int k = lg[r - l + 1];
int ans = st[l][k] & st[r - (1 << k) + 1][k];

验证：数组 7 3 5 6（二进制 111, 011, 101, 110）。
查询 [1,4]：7 & 3 & 5 & 6 = 3 & 5 & 6 = 1 & 6 = 0。
用 ST 表：len = 4, k = 2, 2^k = 4；左段 st[1][2] = 7&3&5&6 = 0，右段 st[1][2] = 0（起点 4-4+1 = 1，两段重合）；0 & 0 = 0 ✓
查询 [2,3]：len = 2, k = 1；st[2][1] = 3&5 = 1，右段起点 3-2+1 = 2，也是 st[2][1] = 1；1 & 1 = 1 ✓（暴力：3&5 = 1）

对照「按位或」：把 & 全部换成 | 即可，同样满足幂等性（x | x = x）。
但「按位异或」不行（x ^ x = 0）——那要用前缀异或。这三个按位运算只差一个符号，可用性却完全不同，这是最容易踩的坑。

C综合编程提高+/省选-

n ≤ 3×10⁵，q ≤ 10⁶ 次询问区间最大值。要求：① 用 ST 表；② 总内存不超过 64 MB（含其他数组）。请给出 K 的取值、数组声明，并写出内存估算过程。

查看参考答案

第一步 · 算出需要多少层。最大 k 满足 2^k ≤ n = 300000。
2¹⁸ = 262144 ≤ 300000，2¹⁹ = 524288 > 300000，所以 最大 k = 18。
由于 k 从 0 开始编号，第二维需要 19 个元素（下标 0~18）。

第二步 · 内存估算。

st[300005][19]：300005 × 19 ≈ 5.7 × 10⁶ 个 int
5.7 × 10⁶ × 4 字节 ≈ 22.8 MB ✓ 远小于 64 MB
加上 a[300005]（1.2 MB）、lg[300005]（1.2 MB），总计约 25 MB，安全。

#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
const int K = 19;                 // 下标 0..18，够放 2^18 = 262144
int n, q, a[N], lg[N];
int st[N][K];                    // 300005 * 19 * 4B ≈ 22.8 MB

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

    for (int i = 1; i <= n; i++) st[i][0] = a[i];

    for (int k = 1; k < K && (1 << k) <= n; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            st[i][k] = max(st[i][k-1], st[i + (1 << (k-1))][k-1]);

    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        int k = lg[r - l + 1];
        printf("%d\n", max(st[l][k], st[r - (1 << k) + 1][k]));
    }
    return 0;
}

逐段解析：① const int N = 300005, K = 19; ——K=19 的来历：最大 k=18（2¹⁸=262144 ≤ 3×10⁵ < 2¹⁹），从 0 编号需 19 个元素；② int st[N][K] ——注意这里第二维直接是 K（19），与前面 st[N][K+1] 的写法不同：因为这里的 K 本身就定义为「需要的元素个数」，两种约定都行，但千万别混用（把 K 当「最大层」却又声明 st[N][K] 就差一个元素）；③ 预处理循环加了双重保险 for (k = 1; k < K && (1 << k) <= n; k++) ——k < K 防第二维越界，(1<<k) <= n 防无效层，两个条件缺一不可；④ 查询部分与 P3865 逐字相同。易错：q 高达 10⁶，输出必须用 printf（或关同步的 cout），否则 TLE——本题的第二个隐藏考点。

如果内存预算只有 16 MB 怎么办？三条出路：
① 把 int 换成 short：若数据范围在 ±32767 内，内存直接减半到 11.4 MB。
② 把 lg 表去掉，改用 __lg()：省下 1.2 MB，但收益有限。
③ 换算法：改用「分块」——块内维护最值，查询时整块 O(1) 取块最值、两端零散部分暴力扫，空间只要 O(n)，查询 O(√n)（或 O(块大小 n/B + B)）。当内存真的不够时，ST 表就该让位给分块。

本题的核心能力不是写代码，而是「先算清内存预算」。竞赛里 90% 的 MLE（内存超限）都是因为没提前算过账。记住这个公式：
内存(MB) = n × (⌊log₂ n⌋ + 1) × sizeof(类型) / 1048576

模块 04

总结提升

把 ST 表放进「区间查询结构」的全景图，再用三个拓展案例延伸到 LCA 与难题实战。

📌核心要点总结

① 适用场景三条铁律

静态（无修改）+ 可重复贡献（max/min/gcd/and/or）+ 大量查询。三条全满足才用 ST 表。

② 定义与转移

st[i][k] = 从 i 开始、长度 2^k 的区间答案。st[i][k] = f(st[i][k-1], st[i+2^k-1][k-1])。外层 k、内层 i，顺序不能反。

③ O(1) 查询的公式

k = lg[len]，答案 = f(st[l][k], st[r-2^k+1][k])。右段起点必须写 r - 2^k + 1，这是最容易错的地方。

④ 可重复贡献是关键前提

要求 f(x, x) = x（幂等）。max/min/gcd/and/or/lcm 满足；求和、异或、计数不满足，需改用前缀和 / 树状数组 / 线段树。

⑤ 复杂度与空间账

预处理 O(n log n)（含 O(n) 的 log 表）、查询 O(1)、空间 O(n log n)。n = 10⁵ 约 7 MB，n = 10⁶ 约 80 MB，n = 10⁷ 会爆。

⑥ 两个常用变形

存下标：把 st 里的值换成下标，就能回答「最值的位置」。二维 ST 表：维度翻倍，空间 O(nm log n log m)，只适合边长几百的矩阵。

🔗 三讲连起来看：三种「区间最值」的选址

单调队列（s3-01）：窗口固定长度、滑动，且数据是流式的 → O(n) 时间、O(k) 空间。只要能滑动，就用它（空间最省）。

二叉堆（s3-02）：候选集合不断动态插入删除（没有「窗口」的概念）→ O(log n) 每次。只要集合会变，就用它。

ST 表（s3-03）：数据静态，但要问任意区间（长度不固定、位置任意）→ O(1) 查询，代价是 O(n log n) 的空间。

一句话记忆：窗口滑动 → 单调队列；动态增删 → 堆；任意静态区间 → ST 表。

🚀拓展案例

拓展 1 · ST 表 + 优先队列（P2048 超级钢琴）

题目大意：长度为 n 的序列，取出 k 个互不相同的子区间（每个子区间长度在 [L, R] 之间），使得这 k 个子区间的和之和最大。n, k ≤ 5×10⁵。

第一步 · 前缀和。子区间 [l, r] 的和 = S[r] - S[l-1]。

第二步 · 固定右端点。固定右端点 r，左端点 p = l-1 的取值范围是 [r-R, r-L]。要让和最大，就要让 S[p] 最小——这是一个区间最小值查询，且数据静态！正是 ST 表的用武之地（注意：这里要求「最小值的位置」，所以 st 要存下标）。

第三步 · 全局贪心。对每个右端点 r，算出它的「最优左端点」和对应的最大和，把这 n-L+1 个候选放进大根堆。每次取出全局最大的一组 (r, p) 累加答案。

第四步 · 分裂。关键技巧：取走 (r, p) 之后，左端点的可行区间 [r-R, r-L] 被 p 分成了两半 [r-R, p-1] 和 [p+1, r-L]。对这两半分别再求一次「S 的最小值位置」，各自作为一个新候选放回堆里。

💡 为什么「分裂」这一步如此巧妙？

因为「同一个右端点 r 的次优解」可能就藏在 p 的左边或右边——只有把区间切开、重新在每一半里取最值，才能保证不会漏掉次优解，也不会重复取到已选的 p。

复杂度：初始建堆 O(n log n)；每次取堆顶 O(log n)；取 k 次。ST 表预处理 O(n log n)、每次区间查询 O(1)。总计 O((n + k) log n)。

这个套路的名字：「堆 + RMQ 的 k 次取最大」，是 NOI 级别的经典组合技。它的通用形态是：维护一堆「区间」，每次取出全局最优的一个，然后用最优位置把区间劈成两半放回去。学名可以叫「分裂式贪心」。

拓展 2 · 倍增求 LCA（P3379 最近公共祖先）

问题：一棵有根树，q 次询问「两个节点的最近公共祖先（LCA）」。

与 ST 表的同构之处：定义 up[u][k] = 「从 u 向上跳 2^k 步所到达的祖先节点」。转移同样是倍增：

up[u][0] = fa[u]                                  // 跳 1 步 = 父亲
up[u][k] = up[ up[u][k-1] ][k-1]                   // 跳 2^k 步 = 先跳 2^(k-1) 步，再跳 2^(k-1) 步

把这个式子与 ST 表对照：

对比项	ST 表	倍增 LCA
状态定义	`st[i][k]`：从 i 开始长度 2^k 的区间答案	`up[u][k]`：从 u 向上跳 2^k 步到达的节点
转移	合并两半：`f(st[i][k-1], st[i+2^k-1][k-1])`	接力跳：`up[up[u][k-1]][k-1]`
预处理	O(n log n)	O(n log n)
回答询问	两段覆盖 → O(1)	逐位跳（把深度差按二进制拆）→ O(log n)

核心代码（求 LCA 的关键两步）：

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);

    // ① 把 u 跳到与 v 同深度：按二进制拆深度差
    int d = dep[u] - dep[v];
    for (int k = 0; d; k++, d >>= 1)
        if (d & 1) u = up[u][k];

    if (u == v) return u;                // v 就是 u 的祖先

    // ② 一起往上跳，直到「再跳一步就相同」为止
    for (int k = LOG; k >= 0; k--)
        if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; }

    return up[u][0];                    // 此时 u、v 的父亲就是 LCA
}

💡 第 ② 步为什么是「从大到小」跳，而不是「从小到大」？

因为我们要找的是「最深的、两个点还不同的祖先层」。如果从小到大跳，可能一步就跳过了 LCA（跳到了 LCA 的上面），就再也回不来了。从大到小跳保证了「贪心地尽量多跳，但绝不越过 LCA」——这和「把整数用二进制表示」的思想完全一致（从高位到低位决定每一位取不取）。

所以：倍增的两个典型用法——ST 表（合并型，向两侧展开）与倍增 LCA（跳跃型，向同一方向递进）——虽然形态不同，但底层都是「用 2 的幂次表示任意规模」这一条原理。学会一个，另一个自然就能理解。

🔍 代码逐段解析 · 倍增求 LCA 的关键两步

第 1 行 if (dep[u] < dep[v]) swap(u, v);：统一约定「u 是更深的那个」——后面只把 u 往上跳，省去分类讨论。易错：忘了 swap 的话，深度差为负，第 1 步的循环直接不出活。

第 ① 步（对齐深度）：int d = dep[u] - dep[v]; for (int k = 0; d; k++, d >>= 1) if (d & 1) u = up[u][k]; ——把深度差 d 看成二进制，第 k 位是 1 就「跳 2^k 步」。精髓：不用真的「跳 d 次」，log 次接力就够了。这里循环变量 k 与 d >>= 1 联动，每一位对应 up 表的一层。

第 ② 步（一起上跳）：for (int k = LOG; k >= 0; k--) if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; } ——从大到小枚举层，只要「跳 2^k 步后两者不同」就大胆跳。易错：写成从小到大就可能一步跳过 LCA 且无法回头（见上方 thought-box）；写成 up[u][k] == up[v][k] 就跳 更是方向性错误——相等说明跳过头了。

第 ③ 行 return up[u][0];：循环结束时 u、v 都停在「LCA 的下一层」，各自再跳 1 步（up[·][0] 即父亲）就是 LCA。易错：返回 u 本身是错的——此时 u 还不是 LCA，它的父亲才是。

前置工作：这份代码依赖两个预处理——每个点的深度 dep[]（一次 DFS/BFS）和整张 up 表（up[u][k] = up[up[u][k-1]][k-1]，O(n log n)）。少了任何一个都会 RE。

拓展 3 · ST 表的对手们：分块与线段树

ST 表不是万能的。当它不适用时，下面这些结构是备选方案：

🧱 分块

空间：O(n)（最省）。查询：O(n/B + B)，取 B = √n 时 O(√n)。支持修改：是。适用：内存吃紧、或需要修改但线段树写不动时的「保底方案」。

🌲 线段树

空间：O(n)。查询：O(log n)。支持修改：是（单点 / 区间皆可）。适用：几乎所有场景的「万能解」，代价是代码长、常数大。

⚡ ST 表

空间：O(n log n)（最贵）。查询：O(1)（最快）。支持修改：否。适用：静态 + 海量查询 + 可重复贡献运算。

三个实用判断：

① n ≤ 10⁵ 且 q 很大（≥ 10⁵）且无修改 → 优先 ST 表，几乎是最优解。

② n ≥ 10⁶ 或内存限制很紧（≤ 64 MB） → 先算内存，不够就换分块或线段树。

③ 有修改操作 → 无条件放弃 ST 表，直接用线段树（或树状数组）。

💡 一个更高级的方向（了解即可）：「猫树（Cat Tree）」。它在 O(n log n) 预处理、O(n log n) 空间下，支持 O(1) 的任意区间查询，而且不要求运算可重复贡献（连求和也能做）。代价是实现复杂度远高于 ST 表。知道它的存在、知道「ST 表的限制有替代方案」就够了，不必现在就去实现。

🤔思考与启发

思考 1：「可重复贡献」要求 f(x, x) = x。请尝试证明：满足交换律、结合律和幂等性的运算，用「两段重叠覆盖」一定不会算错。

提示：设左段覆盖集合 A、右段覆盖集合 B，目标区间 T = A ∪ B。两段的答案分别是 f(A) 和 f(B)。由结合律与交换律，f(f(A), f(B)) = f(A ∪ B) = f(T)——注意这里用到「重叠部分在 A∪B 里只算一个」，而幂等性保证了「重复出现」不会改变结果。反过来，如果 f 不幂等，f(A ∪ B) 就不等于 f(A∪B 里带重复的版本)。

思考 2：为什么 ST 表的第一层（k = 0）不能直接就是「长度为 1 的区间」，而是需要单独用 a[i] 初始化？如果初始化成 0 会怎样？

提示：因为「长度为 1 的区间的最值」就是元素本身，这是一个无法由更小的区间合并得到的基础情形（没有长度 1/2 的区间可以合并）。如果初始化成 0，那么求最大值时所有区间都会得到 ≥ 0 的错误结果（负数的最大值会变成 0）。任何递推式都必须有正确的「基础情形」。

思考 3：ST 表的查询是「两段覆盖」，那能不能用「三段」？四段呢？什么时候用三段会更合适？

提示：可以用更多段，但没意义——两段已经是能覆盖任意区间的最少段数（因为你需要至少两段才能「同时贴住左右两端」）。只有在运算不满足幂等性时才需要更多段，例如「求和」就必须用不重叠的分解（二进制分解），那正是「分块 / 线段树」的思路来源。「用最少的段数完成覆盖」是这类算法设计的核心目标。

思考 4：如果题目要求「支持单点修改 + 查询区间最大值」，还有什么折中方案能在修改不频繁时保留 ST 表的速度优势？

提示：一种思路是「分块重建」——把数组分成若干块，每块内部用 ST 表维护；单点修改时只重建所属的那一块（代价 O(B log B)），查询时整块 O(1) 取块内 ST 表答案、两端的零散元素暴力扫。这样修改 O(B log B)、查询 O(B + n/B)。取 B ≈ √n 时，两者都是 O(√n)——用一点速度换来了修改能力。这就是「时间与功能之间的重新分配」。

模块 05

学习检测

五个最容易出错的地方 + 三张速查表 + 一张笔记卡，考前过一遍。

⚠️高频错误诊断

①层循环与下标循环写反（k 写成内层）

错误写法：for (i = 1; i <= n; i++) for (k = 1; (1<<k) <= n; k++) st[i][k] = max(st[i][k-1], st[i+(1<<(k-1))][k-1]);——这样写会读到还没算出来的第 k−1 层数据，因为 i + 2^k−1 这个位置的第 k−1 层可能还没轮到。

正确写法：外层 k、内层 i。for (int k = 1; (1<<k) <= n; k++) for (int i = 1; i + (1<<k) - 1 <= n; i++) ...
为什么：第 k 层的任何一格都依赖第 k−1 层的两格。所以必须先把整个第 k−1 层算完，才能开始第 k 层。
自检口诀：层在外、位置在内。凡是「按层递推」的 DP（ST 表、倍增 LCA 的预处理、二进制分组背包），都遵循这条。

②右段起点写成 r - (1<<k)

症状：查询结果偶尔偏小（求最大值时）/ 偏大（求最小值时），而且只在「区间长度不是 2 的幂」时出错。

正确公式：r - (1 << k) + 1。推导：右段要「以 r 结尾」且长度 2^k，则 起点 + 2^k - 1 = r，所以 起点 = r - 2^k + 1。
两个边界验证法（强烈建议写完就试）：
① 令 l == r：此时 len = 1, k = 0，起点 = r - 1 + 1 = r，得到 st[r][0] = a[r] ✓
② 令 len == 2：此时 k = 1，起点 = r - 2 + 1 = r - 1，两段都是 [r-1, r] ✓
凡是带 ±1 的公式，都用最短的区间代进去验一遍。

③第二维开小了，越界读写

症状：程序随机出错、RE（运行时错误），或者在小数据上正确、大数据上答案莫名其妙。

原因：把「最大 k 值」和「数组需要多少个元素」搞混了。k 从 0 开始编号，所以如果最大 k = 16，第二维需要 17 个元素（下标 0~16）。写成 st[N][16] 就会越界。
可靠做法：① 直接按经验值放宽——n = 10⁵ 用 18，n = 10⁶ 用 21，n = 10⁷ 用 25；② 更稳妥的是用 const int K = lg(n) + 1; 动态算出来（但这样就不能用静态数组了，要改 vector）；③ 循环条件写 (1<<k) <= n，让上界自动收敛。

④对「不可重复贡献」的运算套 ST 表

症状：答案系统性偏大（求和）或完全错乱（异或），且找不到逻辑错误——因为没有逻辑错误，错在数学前提上。

自查清单（把运算代进 f(x, x) == x）：
· max(x,x)=x ✓ · min(x,x)=x ✓ · gcd(x,x)=x ✓
· x&x=x ✓ · x|x=x ✓ · lcm(x,x)=x ✓
· x+x=2x ✗ 求和禁用
· x^x=0 ✗ 异或禁用
替代方案：求和用前缀和或树状数组；异或用前缀异或；计数用树状数组或线段树。
注意：这个错误非常隐蔽——因为代码看起来「和模板一模一样，只换了一个函数」，跑小数据时有时还会碰巧对（区间长度恰好是 2 的幂时重叠部分为 0，不会出错）。所以一定要用长度不是 2 的幂的区间测一测。

⑤用 (int)log2(len) 取 k，被浮点误差咬到

症状：绝大多数数据都对，但某个特定长度的区间会莫名其妙错一位（例如 len = 8 时算出 k = 2 而不是 3）。

原因：log2() 是浮点函数，返回值可能有微小误差（如 log2(8) 返回 2.9999999999 或 3.0000000001）。直接强制转换取整，前者会得到 2，后者得到 3——结果差一层，查询就会出错，而且只在某些长度上出现，极难调试。
三种正确做法：
① 递推打表（推荐）：lg[1] = 0; for (int i = 2; i <= n; i++) lg[i] = lg[i>>1] + 1;——纯整数运算，绝无误差。
② GCC 内建：__lg(x) 或 31 - __builtin_clz(x)——整数位运算实现，O(1) 无误差。
③ 实在要用浮点，必须写成 (int)(log2(len) + 1e-9)——但依然不推荐，因为在 32 位环境下 log2 的精度可能不足以支撑。
通用原则：能在整数域里算的，绝不用浮点。

📋速查表

表 1 · ST 表完整模板（区间最大值）

const int N = 100005, K = 18;          // K 要满足 2^K > n
int n, q, a[N], st[N][K], lg[N];

// ① log 表 O(n)——纯整数递推，无精度问题
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

// ② 基础情形：长度 1
for (int i = 1; i <= n; i++) st[i][0] = a[i];

// ③ 倍增预处理 O(n log n) —— 层在外、位置在内
for (int k = 1; (1 << k) <= n; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++)
        st[i][k] = max(st[i][k-1], st[i + (1 << (k-1))][k-1]);

// ④ 查询 O(1)
int query(int l, int r) {
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

表 2 · 运算可用性判断表

运算	幂等性 `f(x,x)=x`	能否用 ST 表	若不能，替代方案
区间最大值 max	`max(x,x)=x` ✓	✓ 可以	—
区间最小值 min	`min(x,x)=x` ✓	✓ 可以	—
最大公约数 gcd	`gcd(x,x)=x` ✓	✓ 可以	—
最小公倍数 lcm	`lcm(x,x)=x` ✓	✓ 可以	—
按位与 &	`x&x=x` ✓	✓ 可以	—
按位或 \|	`x\|x=x` ✓	✓ 可以	—
求和 +	`x+x=2x` ✗	✗ 不可	前缀和 / 树状数组 / 线段树
按位异或 ^	`x^x=0` ✗	✗ 不可	前缀异或
计数 / 求个数	不可	✗ 不可	树状数组 / 线段树

表 3 · 区间查询结构选型决策

题目的特征	推荐结构	复杂度
静态 + 任意区间 + 可重复贡献运算 + 查询多	ST 表	预处理 O(n log n)，查询 O(1)
静态 + 任意区间 + 求和 / 异或	前缀和 / 前缀异或	预处理 O(n)，查询 O(1)
静态 + 滑动窗口（长度固定）	单调队列	O(n)，空间 O(k)
有单点修改 + 区间查询	树状数组 / 线段树	O(log n)
有区间修改 + 区间查询	线段树（带 lazy）	O(log n)
动态集合取全局最值	优先队列（堆）	O(log n)
内存极紧（≤ 64 MB）或 n ≥ 10⁶	分块 / 线段树	O(√n) / O(log n)
需要「最值出现的位置」	ST 表存下标	查询 O(1)

📌笔记卡

静态 + 不改 + 可重叠，三个条件才敢用

st[i][k]：从 i 起、2 的 k 次方长

层在外、位置在内，递推才不会乱

k 取长度对数，右段起点 = r − 2^k + 1

两段盖住中间叠，重叠无害只因幂等

求和异或不能用，前缀和才管用

空间 n log n，先算内存再动手

本讲最小可交付

能默写 ST 表的四段代码（log 表、基础情形、倍增预处理、O(1) 查询）；能判断一个运算能不能用 ST 表；能给出任意 n 下的 K 取值与内存估算。

本讲典型陷阱

层与位置循环写反、右段起点差 1、K 开小越界、对不可重复贡献的运算套模板、用浮点 log2 取 k。

下讲衔接

下一讲进入 并查集（Union-Find Set）——它解决的是「动态维护集合的连通性」这类问题，与 ST 表的「静态区间查询」正好互补。两者共同构成了「静态查询 / 动态合并」两条主线的基础工具。

课后练习

分层练习作业

A基础 / B提高 / C挑战，难度递增。C组后附 12 道洛谷原题。

🟢 A组 · 基础巩固（4题）

A1概念题

请说明 ST 表的三条适用前提（静态、可重复贡献、查询多），并各举一个不满足的例子。

查看答案

前提 1 · 数据必须静态（无修改）。
反例：「支持单点修改 + 查询区间最大值」——比如队列操作，随时有新元素加入。修改一个元素会影响 O(log n) 个区间，逐个更新还不如重算整张表。→ 应用线段树。

前提 2 · 运算必须可重复贡献（幂等）。
反例：「查询区间和」——x + x = 2x 不幂等，两段重叠部分会被算两次。→ 应用前缀和。
另一个反例：「查询区间异或」——x ^ x = 0。→ 应用前缀异或。

前提 3 · 查询次数要足够多，才值得花 O(n log n) 预处理。
反例：只有 1 次查询。此时 O(n log n) 的预处理 + O(1) 查询，还不如直接 O(n) 暴力扫一遍来得快。→ 直接暴力。

补充说明：三条前提里，第 2 条最容易被违反也最隐蔽——因为把 max 换成 + 代码几乎不变，小数据（区间长度恰好是 2 的幂）还不会暴露问题。做题时务必先在心里过一遍「这个运算幂等吗」。

A2模板默写

不看笔记，完整写出 ST 表的四段代码（log 表、基础情形、倍增预处理、查询函数），并解释每一行的作用。

查看答案

// ① log 表：lg[i] = floor(log2(i))，纯整数递推 O(n)
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

// ② 基础情形：长度为 1 的区间，答案就是元素本身
for (int i = 1; i <= n; i++) st[i][0] = a[i];

// ③ 倍增预处理：层在外、位置在内
for (int k = 1; (1 << k) <= n; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++)
        st[i][k] = max(st[i][k-1], st[i + (1 << (k-1))][k-1]);

// ④ 查询：两段覆盖
int query(int l, int r) {
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

逐行含义：
① 用「i/2 的对数 = i 的对数 − 1」这条性质递推，避免浮点误差。
② 长度为 1 的区间是递推的起点，不能由更小的区间得出，必须手动填。
③ 每一格由「同一行左边半段」和「右边半段」（起点偏移 2^k−1）合并而来。循环上界 i + 2^k − 1 ≤ n 保证区间不越界。
④ 取 k = lg[len]，用两段长度 2^k 的区间覆盖 [l, r]；右段以 r 结尾，所以起点是 r − 2^k + 1。

自检清单：① K 的第二维够不够（n = 10⁵ 用 18）；② 层与位置的循环顺序；③ 右段起点的 +1；④ 查询前 lg 是否已经算好；⑤ 是否用了 scanf（大数据必备）。

A3推演题

数组 a = [4, 1, 6, 2, 8, 3, 9, 5]（n = 8）。请手写出 k = 0, 1, 2, 3 四层的 st[i][k]（区间最大值），并推演查询 [2, 7] 的过程。

查看答案

k = 0（长度 1）：4 1 6 2 8 3 9 5（就是 a 本身），共 8 个有效起点。

k = 1（长度 2）：max(4,1)=4，max(1,6)=6，max(6,2)=6，max(2,8)=8，max(8,3)=8，max(3,9)=9，max(9,5)=9
→ 4 6 6 8 8 9 9，共 7 个有效起点（8−2+1）。

k = 2（长度 4）：st[i][2] = max(st[i][1], st[i+2][1])
i=1：max(4, 6) = 6；i=2：max(6, 8) = 8；i=3：max(6, 8) = 8；i=4：max(8, 9) = 9；i=5：max(8, 9) = 9
→ 6 8 8 9 9，共 5 个有效起点（8−4+1）。

k = 3（长度 8）：st[1][3] = max(st[1][2], st[5][2]) = max(6, 9) = 9
→ 只有 1 个有效起点。整个数组的最大值是 9 ✓

查询 [2, 7] 的推演：

第 1 步：len = 7 - 2 + 1 = 6
第 2 步：k = lg[6] = 2（因为 2² = 4 ≤ 6 < 8），2^k = 4
第 3 步：左段从 2 开始、长度 4 → 覆盖 [2, 5] → st[2][2] = 8
第 4 步：右段以 7 结尾、长度 4 → 起点 7 - 4 + 1 = 4 → 覆盖 [4, 7] → st[4][2] = 9
第 5 步：两段并集 = [2,5] ∪ [4,7] = [2,7] ✓，重叠部分 [4,5]
第 6 步：ans = max(8, 9) = 9
暴力验证：max{1, 6, 2, 8, 3, 9} = 9 ✓

A4辨析题

ST 表和「分块」都能做静态区间最值。什么时候该选分块？

查看答案

两者的核心差异：

对比项	ST 表	分块
预处理	O(n log n)	O(n)
单次查询	O(1)	O(n/B + B)，取 B = √n 时 O(√n)
空间	O(n log n)（贵）	O(n)（省）
支持修改	否	是（只重建一块，O(B)）
运算要求	必须可重复贡献	无限制（求和也行）
实现难度	简单（20 行）	稍复杂（要处理边界块）

选分块的三种情形：
① 内存不够。n = 10⁶ 时 ST 表要 80 MB、n = 10⁷ 时要 800 MB；而分块永远只要 O(n)。这是分块最主要的用武之地。
② 需要支持修改，但线段树写不出来。分块的修改只需重建所属块，代码比线段树短得多，是很好的「保底方案」。
③ 运算不可重复贡献且需要修改。此时 ST 表彻底无能，前缀和也不行（不支持修改），分块是可行选择之一。
反之选 ST 表：内存够、无修改、查询次数极多（q 达到 10⁶ 以上）。因为 O(1) 和 O(√n) 的差距在 10⁶ 次查询下会被放大到上千倍。

🟡 B组 · 提高训练（4题）

B1编程题

给定 n 个数，q 次询问 [l, r] 中「最大值与最小值的下标之差」（要求取最左的最大值和最左的最小值）。n, q ≤ 10⁵。

查看答案

思路：需要四张信息——最大值位置、最小值位置。用两张「存下标」的 ST 表分别处理。

int greater_idx(int x, int y) {      // 值更大优先；相等取下标小
    if (a[x] != a[y]) return a[x] > a[y] ? x : y;
    return x < y ? x : y;
}
int less_idx(int x, int y) {         // 值更小优先；相等取下标小
    if (a[x] != a[y]) return a[x] < a[y] ? x : y;
    return x < y ? x : y;
}

// 预处理两张表 stMaxPos / stMinPos，初始值都是 i
for (int i = 1; i <= n; i++) stMaxPos[i][0] = stMinPos[i][0] = i;
for (int k = 1; (1 << k) <= n; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++) {
        stMaxPos[i][k] = greater_idx(stMaxPos[i][k-1], stMaxPos[i + (1 << (k-1))][k-1]);
        stMinPos[i][k] = less_idx  (stMinPos[i][k-1], stMinPos[i + (1 << (k-1))][k-1]);
    }

// 查询
int k = lg[r - l + 1], s = r - (1 << k) + 1;
int pmx = greater_idx(stMaxPos[l][k], stMaxPos[s][k]);
int pmn = less_idx  (stMinPos[l][k], stMinPos[s][k]);
printf("%d\n", abs(pmx - pmn));

验证：数组 4 1 6 2 8 3，询问 [1,4]：
区间 {4,1,6,2}，最大值 6 在下标 3，最小值 1 在下标 2 → |3-2| = 1。
询问 [2,6]：区间 {1,6,2,8,3}，最大值 8 在下标 5，最小值 1 在下标 2 → |5-2| = 3。

关键点：① 存下标而不是存值——这是「求位置」类问题的标准做法；② 两个比较函数的「相等时取小下标」保证了「最左」；③ 两张表的下标偏移公式完全相同，可以抽取成一个小函数减少重复；④ 内存是单张表的两倍（两张 st[N][K]）。
延伸提问：如果要求「最大值与最小值第一次出现的位置之差」，但当区间内所有数都相等时，答案应该是 0——验证一下你的代码在这个边界下是否正确。

逐段解析：① greater_idx / less_idx 两个比较器结构对称：第一行分出「值不等」的情况（大者/小者胜），第二行统一 return x < y ? x : y; 处理平局（取小下标=最左）。两个函数的平局分支完全相同，只有第一行的比较方向相反；② 预处理两张表在同一个循环里同步更新，省一次遍历；③ 查询里先算 k = lg[r - l + 1] 和 s = r - (1 << k) + 1，把公共量提成局部变量，mx/mn 两行共用——易错：pmx 用 greater_idx、pmn 用 less_idx，两行长得很像极易抄串，建议写完立刻用 [1,4]={4,1,6,2} 手验一遍（应输出 1）。边界：区间全相等时 pmx == pmn，abs(pmx - pmn) = 0，天然正确——好写法自己兜住边界。

B2编程题

给定 n 个数，q 次询问 [l, r] 内所有数的最小公倍数（答案对 998244353 取模）。请先判断这个运算能不能用 ST 表。

查看答案

第一步 · 判断可用性。逐条检查：

· 交换律：lcm(x, y) = lcm(y, x) ✓
· 结合律：lcm(lcm(x,y), z) = lcm(x, lcm(y,z)) ✓（都等于三者共同的最小公倍数）
· 幂等性：lcm(x, x) = x ✓ ——满足，可以用 ST 表。

第二步 · 但有一个陷阱：取模运算会破坏结合律。lcm 本身满足结合律，但 lcm(a, b) mod p 之后再参与运算，就不等价于「先算出真实 lcm、最后再取模」了——因为取模后的值丢失了信息（比如真实的 lcm 是 998244353 的倍数，取模后变成 0，后续再算 lcm 就会全是 0）。

正确的做法：
① 如果数据范围保证「真实 lcm 不会溢出 long long」，那么整张 ST 表都用真实值（不取模），只在最后输出时取模。但本题的 lcm 会迅速爆炸（n 个数的最小公倍数增长速度远超 2ⁿ），所以这条路走不通。
② 正解：换结构。既然取模破坏了「可重复贡献」的语义，就改用线段树——线段树虽然也取模，但它的合并顺序是「按树形结构两两合并」，可以保证每一层都是「两个子树答案的 lcm 再取模」，只要题目保证中间结果不溢出问题（或者题目本身就按模定义 lcm），就是一致的。
③ 更常见的正解：分解质因数。把每个数分解成质数幂次，对每个质数分别维护「区间最大指数」，用 st 表（因为 max 是可重复贡献的）求出区间内每个质数的最大指数，再乘起来取模。

这道题的价值：它提醒我们「数学上满足可重复贡献」不等于「在取模语义下也满足」。判据要针对你实际使用的运算（这里是「取模后的 lcm」），而不是它背后的数学理想。这是很多「看起来该对却总是错」的题目的根源。

B3编程题

给定 n 个数和 q 次询问，每次问 [l, r] 内最大值减去前一个最大值（若无第二个不同位置的最大值则输出 0）。n, q ≤ 10⁵。

查看答案

关键认识：ST 表不能直接回答这个问题。因为「第二大值」不是可重复贡献的运算——两段的最大值合并能得到全局最大，但「两段的第二大值」合并起来不一定是全局第二大（全局第二可能恰好就是某一段的最大值）。

正确解法的两步：

第 1 步：用「存下标」的 ST 表求出 [l, r] 内最大值的位置 p（取最左）。
第 2 步：把区间拆成 [l, p-1] 和 [p+1, r] 两部分，它们的最大值就是「除了 a[p] 之外的最大值」。取这两部分的最大值中的较大者即为「第二大值」。
如果两部分都为空（即区间内所有元素都在 p 的位置，也就是 l == r），输出 0。

int k = lg[r - l + 1], s = r - (1 << k) + 1;
int p = greater_idx(stPos[l][k], stPos[s][k]);    // 最大值的位置（最左）

long long second = 0;
if (p - 1 >= l) {                            // 左边还有元素
    int len = p - l, kk = lg[len], ss = p - (1 << kk);
    second = max(second, (long long)max(stVal[l][kk], stVal[ss][kk]));
}
if (p + 1 <= r) {                            // 右边还有元素
    int len = r - p, kk = lg[len], ss = r - (1 << kk) + 1;
    second = max(second, (long long)max(stVal[p + 1][kk], stVal[ss][kk]));
}
printf("%lld\n", (long long)a[p] - second);

验证：数组 3 7 1 7 5，询问 [1,5]：最大值 7 最左在下标 2 → 左部分 [1,1] = {3}、右部分 [3,5] = {1,7,5} → 第二大值 = max(3, 7) = 7 → 答案 7 - 7 = 0。

重要启发：ST 表只能回答「单一运算的最值」，遇到「第 k 大」「次大值」这类组合信息时，需要把问题分解成多次 ST 表查询（这里用了 3 次）。
一般化：「区间第 k 大」可以用「主席树」或「归并树」解决，但那些不属于 ST 表的范畴。判断一个结构能不能用，关键看「目标信息是否可以通过合并两段的信息得到」——次大值不行（因为需要知道最大值在哪一段），但「最大值、最小值、gcd」可以。

逐段解析：① int p = greater_idx(stPos[l][k], stPos[s][k]); ——第 1 次 ST 表查询：拿最大值的位置（最左）；② 左分支 if (p - 1 >= l)：p 左边还有元素才查——len = p - l, kk = lg[len], ss = p - (1 << kk) 注意这段区间以 p−1 结尾，右段起点是 (p−1) − 2^kk + 1 = p − 2^kk，所以代码里是 ss = p - (1 << kk)（没有再 +1，因为公式里的 r 在这里是 p−1）；③ 右分支 if (p + 1 <= r)：区间 [p+1, r] 以 r 结尾，右段起点 r - (1 << kk) + 1 恢复标准公式。易错：两个分支的右端点不同（p−1 和 r），起点公式相差一个 +1——这是本题最容易抄错的地方；④ second 初始化为 0 隐含假设「值非负」，若数据有负数应初始化为 −INF 并单独处理「无第二大」的输出条件。

B4编程题

给定 n 个整数（可能有负数），q 次询问 [l, r] 内的最大值和最小值。n ≤ 10⁵，要求内存不超过 16 MB。

查看答案

内存估算。n = 10⁵，最大 k = 16（2¹⁶ = 65536 ≤ 10⁵ < 2¹⁷），所以 K 维需要 17 个元素。

方案 A（两张 int 表）：2 × 100005 × 17 × 4B ≈ 13.6 MB，加上 a（0.4 MB）、lg（0.4 MB）≈ 14.4 MB → 刚好卡进 16 MB，但很危险（编译器的额外开销、栈空间都可能让它超）。

方案 B（合并成一张 pair 表）：每个位置存「最大值和最小值」两个分量。如果两分量都用 int，内存和方案 A 相同。
方案 C（用 short，推荐）：若数据范围在 ±32767 内，把表元素类型换成 short（2 字节），内存直接减半到 6.8 MB，非常安全。

// 用 short 存储：省一半内存，但要求数据范围在 ±32767 内
const int N = 100005, K = 17;
short stMax[N][K], stMin[N][K];     // 2 * 100005 * 17 * 2B ≈ 6.8 MB
int a[N];                          // 原数组保持 int（0.4 MB）
int lg[N];                         // log 表（0.4 MB）
// 总计约 7.6 MB ✓ 安全

方案 D（更彻底：去掉 lg 数组）：用 __lg() 内建函数代替打表，省下 0.4 MB。虽然省得不多，但代码更短。

本题的训练点：内存是一道需要主动计算的题。很多选手看到「n ≤ 10⁵」就想当然地开 int st[100005][20]——20 维会比 17 维多出 1.2 MB，在 16 MB 的限制下可能就是 MLE 与 AC 的差别。
通用流程：① 算最大 k；② 算 K = k+1；③ 算 n × K × sizeof(类型)；④ 与内存限制对照；⑤ 不够就换类型（int → short）或换算法（ST 表 → 分块）。这五步应该在写代码之前完成。

逐段解析（short 版声明）：① short stMax[N][K], stMin[N][K] ——short 2 字节，两表 ≈ 6.8 MB；② int a[N] 保持 int——读入和比较用 int 更安全，只有表用 short 压缩；比较时 short 会自动提升为 int，不损失精度；③ 易错 1：short 上限 32767——若 a[i] 可能达到 ±40000 就会静默溢出（不报错、答案错），用之前必须确认数据范围；易错 2：若 a 存 short 而 st 存 int，反而浪费——压缩要压「占空间最大的那张表」（st 表是 lg 倍于 a 的大头）；④ lg 表保持 int（值只有 0~17，其实也可以用 char lg[N] 再省 0.3 MB，锦上添花）。本题训练点：内存是「算」出来的，不是「感觉」出来的。

🔴 C组 · 综合挑战（4题）

C1综合编程

给定 n 个数的序列，求所有长度在 [L, R] 之间的连续子段中，平均值最大的那个（输出这个最大平均值，保留 3 位小数）。n ≤ 10⁵。

查看答案

思路：二分答案 + 前缀和 + ST 表。这是「求平均值最大」类问题的标准套路。

第 1 步 · 二分什么？二分平均值 x。判定「是否存在子段平均值 ≥ x」。
第 2 步 · 判定条件转化。子段 [l, r] 平均值 ≥ x ⟺ sum(l,r) / len ≥ x ⟺ sum(l,r) - x·len ≥ 0。
把每个数减去 x 得到 b[i] = a[i] - x，令 T 为 b 的前缀和，则条件变成 T[r] - T[l-1] ≥ 0，即 T[r] ≥ T[l-1]。
第 3 步 · 长度限制。子段长度在 [L, R]，所以对固定的 r，p = l-1 的范围是 [r-R, r-L]。要判断是否存在这样的 r 和 p 满足 T[p] ≤ T[r]，即需要求 T 在区间 [r-R, r-L] 上的最小值——静态区间最小值查询，用 ST 表 O(1)！
第 4 步 · 复杂度。二分 60 次（精度 1e-6）；每次 check 需要重建 T（O(n)）+ 建 ST 表（O(n log n)）+ 扫描判定（O(n)）。总计 60 × n log n ≈ 60 × 1.7×10⁶ = 10⁸——有点悬，需要优化。

优化方向：

① 减少二分次数：用固定 40~50 次二分即可达到 1e-6 精度（每次二分区间的长度减半，log2(值域/精度) 就能算出来），不必 60 次。
② 用单调队列代替 ST 表：因为 p 的取值范围 [r-R, r-L] 是长度固定为 R-L+1 的滑动窗口！这正是上一讲的单调队列场景——O(n) 建窗、O(1) 每次取值，比 ST 表更快（空间也更省）。这是一个重要的替换：定长滑动窗口用单调队列，任意区间才用 ST 表。
③ 预处理 lg 表：lg 表只依赖 n，可以在二分之前算一次，不必每次重算。

本题的收获：识别出「二分答案 + 区间最值」这个组合，并且能根据区间是否定长，在 ST 表和单调队列之间正确切换。这两讲的工具在这里汇合了。

C2综合编程

给定 n 个数，q 次询问「区间 [l, r] 内的最大值，能否通过只交换一对元素让区间变得严格递增」？输出每对区间的答案。（进阶：若可以，输出需要交换的两个位置。）

查看答案

第一步 · 判定「已递增」。「严格递增」意味着相邻对全部满足 a[i] < a[i+1]。定义标记数组 bad[i] = (a[i] >= a[i+1]) ? 1 : 0（i = 1..n-1）。
区间 [l, r] 原本就递增 ⟺ bad[l..r-1] 的和为 0 ⟺ 前缀和作差即可 O(1) 判断。

第二步 · 只能交换一对时的判定。经典结论：设 bad 数组中值为 1 的位置有 cnt 个。

· 若 cnt == 0：已经递增，答案「可以」（交换同一对位置或不必交换）。
· 若 cnt ≥ 3：不可能。因为交换一对元素最多影响它左右各一个相邻关系（最多 2 个位置），无法修复 3 处逆序。
· 若 cnt == 1 或 2：可能可以，但需要验证。设逆序发生在下标 x（a[x] > a[x+1]）和 y（a[y] > a[y+1]，x < y）。交换的目标只能是 (a[x], a[y+1]) 或 (a[x+1], a[y])——枚举这两种情况，分别暴力验证交换后 [x-1, y+1] 这个小区间是否递增。

第三步 · 关键：验证时如何避免 O(n)。交换后需要检查的是「[x-1, y+1] 这一段是否严格递增」。因为只有这段会变，其他位置的 bad 标记不受影响。所以：

① 先把 [x-1, y+1] 这段的 bad 之和单独算出来（用前缀和 O(1)）；
② 把交换后的新值临时放进去，重新算这一段的 bad 之和（长度最多是 y - x + 3，而 cnt ≤ 2 意味着 x 和 y 很接近——具体地，如果 cnt ≤ 2，那么逆序点不超过 2 个，验证区间长度很小，可以暴力）；
③ 如果新的 bad 之和为 0，则「可以」。

第四步 · 与 ST 表的关系。如果题目要求「区间最大值/最小值」而不是「是否递增」，可以在验证中改用 ST 表来判断「交换后是否满足严格递增」——例如检查 max(a[l..x-1]) < a[y+1] 这类条件，用 ST 表 O(1) 得到。这是 ST 表用在「区间内是否满足某个全局性质」类问题中的典型场景。

本题的精髓是「先缩小问题规模」：通过分析「交换一对元素最多影响 2 处相邻关系」这个结构性事实，把「全局判定」压缩成「小区间验证」。这种「先想清楚影响范围，再决定用什么数据结构」的思维方式，比记住任何一个模板都重要。

C3综合编程

用 ST 表求「区间最小值的位置」，并支持「单点修改」（修改次数 ≤ 1000）。请设计一个方案，使得单次修改的代价不超过 O(n)，查询仍是 O(1)。

查看答案

核心思路：懒重建。ST 表不支持修改，但题目给的修改次数很少（≤ 1000）。所以采用「标记脏 + 按需重建」的策略：

bool dirty = false;          // ST 表是否已失效
int  dirtyCnt = 0;         // 累计修改次数
const int REBUILD_THRESHOLD = 50;   // 累计多少次要重建

void update(int pos, int val) {
    a[pos] = val;
    dirty = true;
    dirtyCnt++;
}

void ensureValid() {
    if (!dirty) return;
    // 重建整张 ST 表 O(n log n)
    rebuildST();
    dirty = false;
    dirtyCnt = 0;
}

int query(int l, int r) {
    ensureValid();                 // 查询前确保表是最新的
    int k = lg[r - l + 1];
    return min_idx(stPos[l][k], stPos[r - (1 << k) + 1][k]);
}

复杂度分析：设修改总次数为 m（≤ 1000），每次修改后最多重建一次。如果不做批量优化，最坏是 m 次重建 → O(m · n log n)，m = 1000、n = 10⁵ 时约 1000 × 1.7×10⁶ = 1.7×10⁹——超时。

优化 1 · 批量重建（上面的写法）：用一个计数器，累计 50 次修改才重建一次。这样重建次数降到 m/50 = 20 次，总代价 20 × 1.7×10⁶ = 3.4×10⁷ ✓ 可接受。
但在「重建之间」的查询怎么办？这段时间 ST 表里存的是旧值。如果直接查，结果可能错。解决办法：查询时只信任 ST 表给出的位置 p，然后用当前的 a[p] 重新取一次值。因为被修改的位置很少（≤ 50 个），「真正的最小值」要么就是 ST 表给出的位置（若它没被改），要么在被修改的那几个位置里。所以：

int minIdxFast(int l, int r) {
    int p = queryFromST(l, r);            // ST 表给出的候选位置（可能已过期）
    int best = p;
        // 再与「所有被修改过、且落在 [l,r] 内」的位置比较
    for (int q : modifiedPositions)
        if (l <= q && q <= r && a[q] < a[best]) best = q;
    return best;
}

优化后的复杂度：查询 O(1 + |modifiedPositions|) = O(1 + 50) = O(1)（常数 50）；修改 O(1)；每 50 次修改重建一次，均摊到每次修改是 O(n log n / 50)。总代价 O(q + m·n log n / 50) ✓

这个方案的通用名字：「按需重建 / 懒重建」。它的思想与「懒惰删除」一脉相承——不追求时刻保持数据最新，而是在「必要时」才付出重建代价，并用少量额外工作兜住「重建间隙」的正确性。
如果修改次数很多（m 与 n 同阶）：那就不要硬撑 ST 表了，换线段树——线段树的单点修改是 O(log n)，查询是 O(log n)，在这种场景下（修改多、查询也多）是最优解。选择数据结构的第一步永远是「看清操作的频率分布」。

逐段解析（懒重建框架）：① bool dirty + int dirtyCnt 两个状态：dirty 标记「表已过期」，dirtyCnt 统计「过期期间攒了多少次修改」，达到阈值 REBUILD_THRESHOLD=50 才重建；② update() 只做三件事：改 a、置 dirty、计数——O(1)，完全不碰 ST 表；③ ensureValid() 在查询前调用：过期才重建（O(n log n)），重建后清零计数；④ minIdxFast() 的兜底逻辑是点睛之笔：ST 表给出的位置 p 可能已过期，但被修改的位置 ≤ 50 个且都记在 modifiedPositions 里——真最小值要么在 p（没被改过），要么在那 ≤50 个位置里，逐个比较一遍就补上了正确性，代价 O(50)=O(1)。易错：modifiedPositions 必须在每次 update 时同步记录（含位置），重建后清空——漏清空会把已「转正」的位置反复比较，虽不出错但拖慢常数。

C4思维拓展

请设计一个「既能 O(1) 查询任意区间、又不要求运算是可重复贡献」的结构（即：连区间求和也能 O(1) 做）。你的方案是什么？它的代价在哪里？

查看答案

答案：猫树（Cat Tree，也叫「线段树的分治版」）。它是 ST 表的一个著名升级版，专门解决「ST 表不支持求和」这个痛点。

核心思想：分治 + 前缀/后缀信息缓存。

第 1 步 ·对整个数组做分治：取中点 mid，把数组分成 [1, mid] 和 [mid+1, n]，递归两侧。
第 2 步 ·在每个分治节点上，计算该节点覆盖区间内「以 mid 结尾的所有后缀的答案」和「从 mid+1 开始的所有前缀的答案」。
第 3 步 ·对于任意询问 [l, r]，一定存在恰好一个分治节点，使得 l 和 r 分别落在它的中点两侧（即 l ≤ mid < r）。此时答案 = 「以 mid 结尾、起点为 l 的后缀答案」 与 「从 mid+1 开始、终点为 r 的前缀答案」 的合并。
第 4 步 ·因为每个节点上这些前缀/后缀答案都已经预处理好了，所以查询就是 O(1) 的两次数组访问 + 一次合并。而且两段完全不重叠（左段到 mid 结束、右段从 mid+1 开始），所以对求和也完全正确！

代价在哪里？

代价 1 · 定位节点需要 O(log n)。「找到那个中点恰好夹住 l 和 r 的节点」这个过程，如果朴素地沿树往下走，是 O(log n) 的。为了让定位也变成 O(1)，通常用「按层存储」+ LCA 技巧（两个叶子的 LCA 就是那个分界节点），配合 O(1) 的 LCA——这又引出了「欧拉序 + ST 表求 O(1) LCA」。整个方案的复杂度层层叠加。
代价 2 · 空间是 ST 表的约 2 倍。每个节点要存前缀和后缀两份信息，总空间约 2n log n（ST 表是 n log n）。n = 10⁵ 时约 14 MB，尚可；n = 10⁶ 时要 140 MB，开始吃紧。
代价 3 · 实现复杂度远高于 ST 表。要处理分治、按层建表、LCA 定位、边界情况……代码量大概是 ST 表的 5~10 倍，且极易写错。竞赛中除非确实需要「O(1) 的任意区间求和」这种苛刻要求，否则几乎不会用到它。

如果只是要 O(1) 求和的替代方案呢？

那当然是用前缀和！O(n) 预处理、O(1) 查询、不需要任何复杂结构。猫树的价值在于「同一个结构能同时处理多种运算」（求和、最值、计数……全都行），因为它的两段是不重叠的，不依赖幂等性。
所以本题真正的答案有两个层次：
① 只求区间和 → 前缀和，简单到极致。
② 要求「通用运算」都能 O(1) → 猫树，代价是实现复杂、空间翻倍。
前者告诉我们「针对特定问题的最简解法往往是最好的」；后者告诉我们「通用性的代价总是昂贵的」。这两条工程直觉，比任何一个数据结构本身都更有价值。

🏆 洛谷原题精选（12道）

以下 12 道题覆盖 ST 表本身、倍增思想、以及 ST 表与其他结构的组合应用，按难度递增排列。

P3865
【模板】ST 表 & RMQ 问题普及/提高-

P2251
质量检测（区间最小值）普及-

P2032
扫描（区间最大值）普及-

P1816
忠诚（区间最小值）普及/提高-

P2880
[USACO07JAN] Balanced Lineup G普及/提高-

P1890
gcd区间（可重复贡献的应用）普及/提高-

P1226
【模板】快速幂（倍增思想入门）普及/提高-

P1198
[JSOI2008] 最大数普及+/提高

P1613
跑路（倍增 Floyd）普及+/提高

P3379
【模板】最近公共祖先（LCA）普及/提高-

P1967
[NOIP2013 提高组] 货车运输提高+/省选-

P2048
[NOI2010] 超级钢琴提高+/省选-

情景导航

放大镜叠加 = 两段覆盖

存零钱的倍数面额 = 倍增

预先做好的成绩统计表 = 预处理

不能再改的档案 = 静态数据

知识探究

为什么 ST 表选第二种而不是第一种？

递推的三个细节

✅ 该用 ST 表

❌ 不该用 ST 表

空间账：二维 ST 表的代价

实践应用

给定 n 个数和 q 次询问，每次询问 [l, r] 内最大值第一次出现的下标（若有多个相同最大值，取最左的那个）。n ≤ 105。

给定 n 个数，q 次询问 [l, r] 内所有数的按位与（AND）。n, q ≤ 105。

n ≤ 3×105，q ≤ 106 次询问区间最大值。要求：① 用 ST 表；② 总内存不超过 64 MB（含其他数组）。请给出 K 的取值、数组声明，并写出内存估算过程。

总结提升

拓展 1 · ST 表 + 优先队列（P2048 超级钢琴）

拓展 2 · 倍增求 LCA（P3379 最近公共祖先）

拓展 3 · ST 表的对手们：分块与线段树

🧱 分块

🌲 线段树

⚡ ST 表

学习检测

表 1 · ST 表完整模板（区间最大值）

表 2 · 运算可用性判断表

表 3 · 区间查询结构选型决策

分层练习作业

🟢 A组 · 基础巩固（4题）

请说明 ST 表的三条适用前提（静态、可重复贡献、查询多），并各举一个不满足的例子。

不看笔记，完整写出 ST 表的四段代码（log 表、基础情形、倍增预处理、查询函数），并解释每一行的作用。

数组 a = [4, 1, 6, 2, 8, 3, 9, 5]（n = 8）。请手写出 k = 0, 1, 2, 3 四层的 st[i][k]（区间最大值），并推演查询 [2, 7] 的过程。

ST 表和「分块」都能做静态区间最值。什么时候该选分块？

🟡 B组 · 提高训练（4题）

给定 n 个数，q 次询问 [l, r] 中「最大值与最小值的下标之差」（要求取最左的最大值和最左的最小值）。n, q ≤ 105。

给定 n 个数，q 次询问 [l, r] 内所有数的最小公倍数（答案对 998244353 取模）。请先判断这个运算能不能用 ST 表。

给定 n 个数和 q 次询问，每次问 [l, r] 内最大值减去前一个最大值（若无第二个不同位置的最大值则输出 0）。n, q ≤ 105。

给定 n 个整数（可能有负数），q 次询问 [l, r] 内的最大值和最小值。n ≤ 105，要求内存不超过 16 MB。

🔴 C组 · 综合挑战（4题）

给定 n 个数的序列，求所有长度在 [L, R] 之间的连续子段中，平均值最大的那个（输出这个最大平均值，保留 3 位小数）。n ≤ 105。

给定 n 个数，q 次询问「区间 [l, r] 内的最大值，能否通过只交换一对元素让区间变得严格递增」？输出每对区间的答案。（进阶：若可以，输出需要交换的两个位置。）

用 ST 表求「区间最小值的位置」，并支持「单点修改」（修改次数 ≤ 1000）。请设计一个方案，使得单次修改的代价不超过 O(n)，查询仍是 O(1)。

请设计一个「既能 O(1) 查询任意区间、又不要求运算是可重复贡献」的结构（即：连区间求和也能 O(1) 做）。你的方案是什么？它的代价在哪里？

🏆 洛谷原题精选（12道）

给定 n 个数和 q 次询问，每次询问 [l, r] 内最大值第一次出现的下标（若有多个相同最大值，取最左的那个）。n ≤ 10⁵。

给定 n 个数，q 次询问 [l, r] 内所有数的按位与（AND）。n, q ≤ 10⁵。

n ≤ 3×10⁵，q ≤ 10⁶ 次询问区间最大值。要求：① 用 ST 表；② 总内存不超过 64 MB（含其他数组）。请给出 K 的取值、数组声明，并写出内存估算过程。

给定 n 个数，q 次询问 [l, r] 中「最大值与最小值的下标之差」（要求取最左的最大值和最左的最小值）。n, q ≤ 10⁵。

给定 n 个数和 q 次询问，每次问 [l, r] 内最大值减去前一个最大值（若无第二个不同位置的最大值则输出 0）。n, q ≤ 10⁵。

给定 n 个整数（可能有负数），q 次询问 [l, r] 内的最大值和最小值。n ≤ 10⁵，要求内存不超过 16 MB。

给定 n 个数的序列，求所有长度在 [L, R] 之间的连续子段中，平均值最大的那个（输出这个最大平均值，保留 3 位小数）。n ≤ 10⁵。