第 45 章 倍增¶
配套例题：BISHI64 【模板】快速幂、BISHI124 【模板】最近公共祖先（LCA）、 BISHI125 【模板】静态区间最值 来源：S3 day8 树上算法（LCA 倍增）、day6
pow.cpp；S4模板.docx的 「倍增 LCA」与「RMQ」两节
倍增（binary lifting）= 把「走 \(k\) 步」拆成二进制，预处理出「走 \(2^j\) 步」的结果。
一句话原理：任何非负整数都能唯一写成若干个不同 \(2^j\) 之和（即二进制表示）， 所以只要预处理出 \(\log k\) 个「跳板」，任意步数都能用 \(\le \log k\) 次跳跃拼出来。
跳板层数 LOG 怎么定：要能表示的最大步数是 \(K\)，就需要 \(j = 0,1,\ldots,\lfloor\log_2 K\rfloor\)，
共 \(\lfloor\log_2 K\rfloor + 1\) 层。Python 里直接写 LOG = K.bit_length() 即可
（\(K \ge 1\) 时 K.bit_length() 恰好等于 \(\lfloor\log_2 K\rfloor + 1\)）。
树上跳祖先时 \(K = n\)（深度不会超过点数），所以 LOG = n.bit_length()；
开小一层就会在最深的链上跳不到位，开大只是多浪费一点内存。
| 对象 | 「一步」是什么 | 「\(2^j\) 步」的合并 | 用途 |
|---|---|---|---|
| 数的乘法 | \(\times a\) | \(a^{2^j} = (a^{2^{j-1}})^2\) | 快速幂 |
| 树上的父指针 | 跳到父亲 | \(fa_{j}[v] = fa_{j-1}[fa_{j-1}[v]]\) | LCA、\(k\) 级祖先 |
| 区间最值 | 长度 1 的区间 | \(st_j[i] = \max(st_{j-1}[i], st_{j-1}[i+2^{j-1}])\) | ST 表 |
| 序列上的转移 | \(i \to nxt[i]\) | 同父指针 | 「至少走多少段能覆盖」 |
| 矩阵 | \(\times M\) | \(M^{2^j}\) | 矩阵快速幂加速递推 |
倍增和二分是一枚硬币的两面：二分是「从大区间往下砍」，倍增是「从大步长往下试跳」。 S3 的二分课件把倍增列在「二分的拓展」里，正是这个道理。
45.1 快速幂¶
Python 里的正确答案：内置 pow¶
三参数 pow 就是快速幂，而且 CPython 对大指数还会自动切换到 5-bit 滑动窗口算法，
比任何手写 Python 循环快一个数量级。
| 写法 | \(T = 2\times10^5\) 组、\(b \le 10^9\) 的耗时 | 说明 |
|---|---|---|
pow(a, b, p) |
约 0.3 s | 全在 C 层 |
手写 while b: 循环 |
约 3 s | \(2\times10^5 \times 30 = 6\times10^6\) 次 Python 迭代 |
在 Python 里手写快速幂 = 自我惩罚。 但你仍然必须会写， 因为矩阵快速幂、快速乘、以及任何「自定义乘法」的场景，内置
pow都帮不上忙。
手写模板（理解原理 + 改造成矩阵版）¶
def qpow(a, b, m):
"""a^b mod m，O(log b)。Python 里请直接用 pow(a, b, m)。"""
res = 1 # 乘法的单位元；换成矩阵版时这里要改成单位矩阵
a %= m # 先约一次，后面每步的中间结果都不超过 m^2
# 循环不变量：进入每轮时，res * a^b 恒等于最初的 a^b（模 m 意义下）
while b:
if b & 1: # 当前二进制位是 1 -> 把这个跳板乘进答案
res = res * a % m
a = a * a % m # 跳板翻倍：a^(2^j) -> a^(2^(j+1))
b >>= 1 # b 每轮减半，循环次数就是 b 的二进制位数
return res % m # 最后再取一次模：m == 1 且 b == 0 时 res 还是 1，必须压成 0
m == 1是快速幂模板的头号坑：res初值是 1，若 \(b = 0\) 直接返回 1， 而正确答案是 \(1 \bmod 1 = 0\)。所以return res % m那次多余的取模不能省。 内置pow(1, 0, 1)返回 0，不会犯这个错。
改造成矩阵快速幂¶
把「乘法」换成矩阵乘法、「1」换成单位矩阵，框架一字不改：
def mat_mul(A, B, m):
n, p, q = len(A), len(B), len(B[0]) # A 是 n x p，B 是 p x q，结果是 n x q
C = [[0] * q for _ in range(n)]
for i in range(n):
Ai = A[i] # 提前绑定，省掉内层的重复下标运算
Ci = C[i]
for k in range(p):
if Ai[k]: # 稀疏矩阵里 0 很多，跳过能省掉整条内层循环
v = Ai[k]
Bk = B[k]
for j in range(q):
Ci[j] = (Ci[j] + v * Bk[j]) % m # i-k-j 顺序，缓存友好
return C
def mat_pow(A, b, m):
n = len(A)
# 单位矩阵是矩阵乘法的单位元，对应标量快速幂里的 res = 1
res = [[1 if i == j else 0 for j in range(n)] for i in range(n)] # 单位矩阵
while b: # 框架与 qpow 一字不差，只换了乘法和单位元
if b & 1:
res = mat_mul(res, A, m) # 这一位是 1，把跳板 A^(2^j) 乘进答案
A = mat_mul(A, A, m) # 跳板翻倍：A^(2^j) -> A^(2^(j+1))
b >>= 1
return res
矩阵快速幂加速线性递推的用法见 104-DP优化 与 85-基础数学与递推。
45.2 ST 表：静态区间最值¶
ST 表（Sparse Table，稀疏表）= 倍增在「区间」上的应用， 用来解决 RMQ（Range Minimum/Maximum Query，区间最值查询）：数组不变，反复问某段的最大或最小值。 \(st_j[i]\) 表示从 \(i\) 开始、长度为 \(2^j\) 的区间（即闭区间 \([i,\ i+2^j-1]\)）的最值。
查询 \([l, r]\) 时取 \(k = \lfloor \log_2(r-l+1) \rfloor\)，用两个长度为 \(2^k\) 的区间覆盖
（它们会重叠，但 max 是幂等的，重叠无所谓）：
def build_st(a, op=max):
"""构建 ST 表。O(n log n) 预处理，O(1) 查询。st[j][i] = a[i .. i+2^j-1] 的最值。"""
st = [a] # 第 0 层：长度 2^0 = 1 的区间就是元素本身
j = 1
n = len(a)
# 层数上界：长度 2^j 的区间必须放得下，所以循环到 2^j > n 为止，共 ⌊log2(n)⌋+1 层
while (1 << j) <= n:
half = 1 << (j - 1) # 把长 2^j 的区间劈成两段长 2^(j-1) 的
prev = st[j - 1]
# map 在较短的可迭代对象耗尽时停止，正好产出 n - 2^j + 1 个合法起点
st.append(list(map(op, prev, prev[half:]))) # 整层一次算完，全在 C 层
j += 1
return st
def query_st(st, l, r, op=max):
"""查询闭区间 [l, r]（0-indexed）。"""
k = (r - l + 1).bit_length() - 1 # ⌊log2(len)⌋，保证 2^k <= 区间长 < 2^(k+1)
# 用两段长 2^k 的区间盖住 [l, r]：一段贴左端、一段贴右端，中间必然重叠
# 重叠无害是因为 max/min 幂等（同一个元素算两次不影响结果）
return op(st[k][l], st[k][r - (1 << k) + 1])
list(map(max, prev, prev[half:]))是本章最值钱的一行 Python 技巧。map遇到较短的可迭代对象就停止，正好得到长度 \(n - 2^j + 1\) 的新层， 而整层的比较全在 C 层完成。手写for i in range(...)要慢 5–10 倍， \(n = 5\times10^5\) 时这就是 AC 与 TLE 的分界。
ST 表适用的运算：必须满足结合律 + 幂等性（\(x \circ x = x\)）。
| 运算 | 能用 ST 表？ | 原因 |
|---|---|---|
max / min |
✅ | 幂等，重叠无害 |
gcd |
✅ | 幂等 |
| 按位与 / 按位或 | ✅ | 幂等 |
| 加法 | ❌ | 不幂等，重叠部分会被算两次 → 用前缀和 |
| 乘法 | ❌ | 同上 |
| 区间最值的四种方案 | 预处理 | 查询 | 支持修改 |
|---|---|---|---|
| 暴力 | \(O(1)\) | \(O(n)\) | ✅ |
| ST 表 | \(O(n\log n)\) | \(O(1)\) | ❌ |
| 线段树 | \(O(n)\) | \(O(\log n)\) | ✅ |
| 单调队列（仅定长滑窗） | — | 均摊 \(O(1)\) | — |
静态区间最值就用 ST 表，别上线段树——Python 里线段树的常数是灾难。 滑动窗口最值用单调队列，见 43-双指针与滑动窗口。
45.3 LCA 倍增¶
对照 S4 模板.docx 的 C++ 倍增 LCA，Python 版的三个步骤：
① 预处理深度与直接父亲（用 BFS，不要用递归 DFS——\(n = 5\times10^5\) 时必爆栈）：
from collections import deque
dep = [0] * (n + 1) # dep[v] = 0 兼作「尚未访问」的标记
fa = [[0] * (n + 1) for _ in range(LOG)] # fa[j][v] = v 往上跳 2^j 步到达的点
dep[root] = 1 # 根深度设为 1，好让 0 空出来当未访问标记
order = [root]
for u in order: # 直接把列表当队列用，边遍历边追加
for v in g[u]:
if dep[v] == 0: # 未访问过 -> 它是 u 的儿子（树上无重边）
dep[v] = dep[u] + 1
fa[0][v] = u # 第 0 层：跳 2^0 = 1 步就是直接父亲
order.append(v)
② 倍增表：\(fa_j[v] = fa_{j-1}[fa_{j-1}[v]]\)
# fa[j][v] = fa[j-1][fa[j-1][v]]：跳 2^j 步 = 先跳 2^(j-1) 步，再跳同样多
# 必须按 j 从小到大算，第 j 层依赖第 j-1 层
for j in range(1, LOG):
prev = fa[j - 1]
fa[j] = [prev[prev[v]] for v in range(n + 1)] # 整层列表推导，C 层循环
③ 查询：先把深的那个提到同一层，再一起往上跳到「父亲相同但自己不同」为止。
def lca(x, y):
if dep[x] < dep[y]:
x, y = y, x # 统一约定：x 是更深的那个
d = dep[x] - dep[y] # 需要把 x 往上提的步数
j = 0
while d: # 把 d 拆成二进制，是 1 的位就跳对应的跳板
if d & 1:
x = fa[j][x]
d >>= 1
j += 1
if x == y: # y 本身就是 x 的祖先，提上来就重合了
return x
# 从大到小试跳：先试大步长，跳不动再换小的，才能保证每一步都是「尽量跳」
# 若从小到大跳，跳过一次小步之后大步就可能越过 LCA，凑不出精确步数
for j in range(LOG - 1, -1, -1): # 从大到小试跳：跳完仍不同才跳
if fa[j][x] != fa[j][y]: # 跳完仍不同 -> 没越过 LCA，这一跳安全
x = fa[j][x]
y = fa[j][y]
return fa[0][x] # 循环结束时 x、y 停在 LCA 的两个不同儿子上
第二个循环为什么是「不同才跳」？ 我们要找的是「最深的、仍然不是公共祖先的位置」。若 \(fa_j[x] = fa_j[y]\)， 说明跳过头了（跳到了公共祖先或更上面），这一步就不能跳。 最后 \(x, y\) 停在 LCA 的两个不同儿子上，
fa[0][x]即答案。 写成if fa[j][x] == fa[j][y]: x = fa[j][x]是最常见的错法。
注意 fa[*][0] = 0：把 0 号点当作「虚拟的根的父亲」，跳出树时自动停在 0，
不需要边界判断。这是倍增数组开 \(n+1\) 长、下标从 1 开始的原因。
| LCA 的三种实现 | 预处理 | 单次查询 | Python 评价 |
|---|---|---|---|
| 倍增 | \(O(n\log n)\) | \(O(\log n)\) | 通用，本章模板 |
| 欧拉序 + ST 表 | \(O(n\log n)\) | \(O(1)\) | 查询快，但欧拉序要 \(2n\) 长 |
| Tarjan（离线） | \(O(n + q)\) | 均摊 \(O(1)\) | 最快，但必须离线且要并查集 |
45.4 序列倍增¶
倍增不只在树上。凡是形如「从 \(i\) 出发，一步走到 \(nxt[i]\)」的函数图， 都能用同一套模板回答「从 \(i\) 出发走 \(k\) 步到哪」或「最少走多少步能超过某位置」。
# nxt[i]: 从 i 出发一步能到的位置（比如「覆盖 i 的区间的最右端 + 1」）
up = [nxt] # up[j][i] = 从 i 出发走 2^j 步到达的位置
for j in range(1, LOG):
prev = up[j - 1]
up.append([prev[prev[i]] for i in range(n + 1)]) # 走 2^j 步 = 走两次 2^(j-1) 步
def jump(i, k):
"""从 i 出发走 k 步。"""
j = 0
while k: # 把 k 拆成二进制，是 1 的位就用对应的跳板
if k & 1:
i = up[j][i]
k >>= 1
j += 1
return i # 循环次数 = k 的二进制位数，即 O(log k)
def min_steps(i, target):
"""从 i 出发，最少多少步能到达 >= target 的位置。从大到小试跳。"""
steps = 0
# 不变量：每轮结束时 i 仍 < target，且 steps 是「保持 i < target」能走的最多步数
for j in range(LOG - 1, -1, -1):
if up[j][i] < target: # 跳完还没到 -> 这一跳不会跳过头，可以放心跳
i = up[j][i]
steps += 1 << j
return steps + 1 # 停在最后一个够不着的位置，再走一步必然到达
「从大到小试跳，跳完仍不满足才跳」是倍增的通用查询范式， LCA 的第二个循环、序列倍增的
min_steps、树上求 \(k\) 级祖先，用的都是它。 它和二分答案的「求最大可行解」在逻辑上完全同构。
典型应用：区间覆盖问题的「最少用几个区间覆盖 \([L, R]\)」、 NOIp 2012《疫情控制》里「军队向上走到哪」（S3 二分课件第 60 页）。
45.5 例题¶
BISHI64 【模板】快速幂（中等）¶
\(T \le 2\times10^5\) 组，每组求 \(a^b \bmod p\)，\(a, b \le 10^9\)，\(p \le 10^9\)。 题面见 BISHI64 原题（牛客）。
import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
ap = out.append
idx = 1 # data[0] 是组数，数据从下标 1 开始，每组吃掉 3 个 token
for _ in range(t):
a = int(data[idx]); b = int(data[idx + 1]); p = int(data[idx + 2])
idx += 3
# 内置三参数 pow = C 实现的快速幂；它对 p == 1 也返回 0，不必像手写版那样补取模
ap(str(pow(a, b, p)))
sys.stdout.write("\n".join(out) + "\n")
main()
三个要点：
p可以等于 1，此时答案恒为 0。样例第一行1 0 1就在考这个—— 手写快速幂若忘了最后一次% p会输出 1。内置pow天然正确。- \(T = 2\times10^5\)，瓶颈在 IO 和
int()解析，不在幂运算。 必须整块读入 + 一次性输出。 a可以为 0（题目只保证 \(a + b > 0\)，排除了 \(0^0\)），pow(0, b, p)对 \(b\ge1\) 返回 0。
题解见 solutions/BISHI64.py，
模运算与逆元见 81-快速幂与逆元。
BISHI125 【模板】静态区间最值（中等）¶
\(n, q \le 5\times10^5\)，\(|a_i| \le 10^9\)。每次询问区间最小值（
op=1）或最大值（op=2）。 题面见 BISHI125 原题（牛客）。
ST 表模板题，同时维护 min 和 max 两张表：
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = list(map(int, data[2:2 + n]))
mx = [a] # mx[j][i] = a[i .. i+2^j-1] 的最大值
mn = [a] # mn[j][i] 同理，最小值
j = 1
while (1 << j) <= n: # 层数上界：长 2^j 的区间必须放得下
half = 1 << (j - 1) # 把长 2^j 的区间劈成两段长 2^(j-1) 的
pm, pn = mx[j - 1], mn[j - 1]
# 错位切片 + map：map 在短的一侧耗尽时停止，正好产出 n-2^j+1 个合法起点
mx.append(list(map(max, pm, pm[half:]))) # 整层用 C 层 map 一次算完
mn.append(list(map(min, pn, pn[half:])))
j += 1
out = []
ap = out.append
p = 2 + n # 询问区起点，每个询问 3 个 token
for _ in range(q):
# 题面 1-indexed，减 1 转成 0-indexed 的闭区间 [l, r]
op = data[p]; l = int(data[p + 1]) - 1; r = int(data[p + 2]) - 1; p += 3
k = (r - l + 1).bit_length() - 1 # ⌊log2(区间长度)⌋
if op == b"1": # op 未解码，比较的是 bytes 字面量
row = mn[k]
# 两段长 2^k 的区间：一段贴左端 l，一段贴右端 r；重叠无害因为 min 幂等
v = row[l]; w = row[r - (1 << k) + 1]
ap(v if v < w else w) # 内联比较，省掉 5e5 次函数调用
else:
row = mx[k]
v = row[l]; w = row[r - (1 << k) + 1]
ap(v if v > w else w)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
四个要点：
(r - l + 1).bit_length() - 1求 \(\lfloor\log_2\rfloor\)： 比math.log2快且不会有浮点误差。math.log2(8)万一算成2.9999999，int()之后就是 2，区间覆盖不全直接 WA。整数的对数一律用bit_length。- 两个区间允许重叠，因为
max/min幂等。这是 ST 表 \(O(1)\) 查询的关键。 - 查询里内联
v if v < w else w而不是min(v, w)： \(5\times10^5\) 次查询下，省掉的函数调用开销是实打实的。 - \(n = q = 5\times10^5\) 在 Python 里是极限规模。建表是 \(\log n = 19\) 层
C 层
map，很快；真正的瓶颈是 \(5\times10^5\) 次查询的 Python 循环。 牛客给「其他语言」10 秒，加上上面这些常数优化才有把握。
本题的题解文件尚未建立，上面这份代码已用官方样例本地实测通过， 但未在牛客实际提交，\(5\times10^5\) 规模下的表现请自行验证。
BISHI124 【模板】最近公共祖先（LCA）（中等）¶
\(N, M \le 5\times10^5\)，给定以 \(R\) 为根的树，\(M\) 次询问两点的 LCA。 题面见 BISHI124 原题（牛客）。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); root = int(data[2])
# 链式前向星建图：比 list of list 省内存，也避开 5e5 个小列表的开销
head = [0] * (n + 1) # head[u]：u 的第一条出边编号，0 表示没有
nxt = [0] * (2 * n) # nxt[e]：与 e 同起点的下一条边，0 表示到头
to = [0] * (2 * n) # to[e]：边 e 指向的点
cnt = 0 # 边计数从 1 开始，把 0 留给「空」
p = 3
for _ in range(n - 1):
x = int(data[p]); y = int(data[p + 1]); p += 2
# 头插法建双向边：新边接到原链表头部，head 指向它
cnt += 1; to[cnt] = y; nxt[cnt] = head[x]; head[x] = cnt
cnt += 1; to[cnt] = x; nxt[cnt] = head[y]; head[y] = cnt
# 树高不超过 n，跳板层数取 n.bit_length() 即 ⌊log2 n⌋+1 层，足够覆盖任意跳跃步数
LOG = max(1, n.bit_length())
dep = [0] * (n + 1) # dep[v] == 0 兼作「尚未访问」标记
fa = [[0] * (n + 1) for _ in range(LOG)] # fa[j][v]：v 往上跳 2^j 步到达的点
# BFS 求深度与直接父亲：n 到 5e5，递归 DFS 必然爆栈
order = [root]
dep[root] = 1 # 根深度设为 1，0 空出来当未访问标记
f0 = fa[0]
for u in order: # 边遍历边追加，列表在迭代中扩展是安全的
e = head[u]
while e: # 沿链表走完 u 的所有出边，e == 0 即到头
v = to[e]
if dep[v] == 0: # 没访问过 -> v 是 u 的儿子
dep[v] = dep[u] + 1
f0[v] = u # 第 0 层跳板：跳 2^0 = 1 步就是直接父亲
order.append(v)
e = nxt[e]
# fa[j][v] = fa[j-1][fa[j-1][v]]：跳 2^j 步等于连着跳两次 2^(j-1) 步
# fa[*][0] = 0 天然成立，跳出树顶后停在 0，查询里不必写边界判断
for j in range(1, LOG):
prev = fa[j - 1]
fa[j] = [prev[prev[v]] for v in range(n + 1)] # 倍增表，整层一次建好
out = []
ap = out.append
for _ in range(m):
x = int(data[p]); y = int(data[p + 1]); p += 2
if dep[x] < dep[y]:
x, y = y, x # 统一约定：x 是更深的那个
d = dep[x] - dep[y] # 深度差，按二进制拆成若干次跳跃
j = 0
while d: # 先把深的那个提到同一层
if d & 1:
x = fa[j][x]
d >>= 1
j += 1
if x != y: # 相等说明 y 原本就是 x 的祖先，直接就是答案
# 从大到小试跳：大步优先才能保证每步都「尽量跳」而不越过 LCA
for j in range(LOG - 1, -1, -1):
if fa[j][x] != fa[j][y]: # 跳完仍不同 -> 没跳过头，可以放心跳
x = fa[j][x]
y = fa[j][y]
x = fa[0][x] # 此时 x、y 停在 LCA 的两个不同儿子上
ap(x)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
五个要点：
- BFS 代替递归 DFS：\(n = 5\times10^5\) 时递归必爆栈；
for u in order:一边遍历一边append是 Python 里最省事的 BFS 写法 （列表在迭代中扩展是安全的）。 - 链式前向星：\(5\times10^5\) 个
list对象每个至少 56 字节， 邻接表要 30 MB+；三个整数数组只要几 MB。见 90-图的表示与遍历。 fa[j] = [prev[prev[v]] for v in range(n+1)]：整层用列表推导建， 比逐点赋值快 2 倍以上。- 0 号点当哨兵：
fa[*][0] = 0，跳出树顶自动停住，查询里不用写边界判断。 x == y要先判：若 \(y\) 本身就是 \(x\) 的祖先，提到同层后两者已相等， 此时直接返回，进第二个循环会出错。
Python 现实性提醒：\(N = M = 5\times10^5\)、\(\log = 19\)， 建表 \(10^7\) 次操作 + 查询 \(10^7\) 次 Python 层循环，即便有 10 秒时限也非常紧张。 若 TLE，可行的替代路线是欧拉序 + ST 表（把查询降到 \(O(1)\)， 且建表能用 45.2 的 C 层
map技巧），或者离线 Tarjan。 本题的题解文件尚未建立，上面的代码只用官方样例本地实测通过， 大规模数据下的表现未经验证。
45.6 本章速查¶
| 需求 | 做法 |
|---|---|
| \(a^b \bmod m\) | pow(a, b, m)，别手写 |
| 手写快速幂 | 最后要 % m，否则 \(m=1\) 时错 |
| 自定义乘法（矩阵等） | 手写快速幂框架，换掉乘法和单位元 |
| 静态区间最值 | ST 表，\(O(n\log n)\) 建 + \(O(1)\) 查 |
| ST 表建表 | list(map(max, prev, prev[half:]))，整层 C 层完成 |
| \(\lfloor\log_2 x\rfloor\) | x.bit_length() - 1，不要用 math.log2 |
| ST 表适用运算 | 需幂等：max/min/gcd/&/\|；加法不行 |
| 区间和 | 前缀和，不是 ST 表 |
| 滑窗最值 | 单调队列，不是 ST 表 |
| LCA | 倍增；\(n\) 大时 BFS 求深度，别递归 |
| LCA 第二阶段 | fa[j][x] != fa[j][y] 才跳 |
| 倍增数组哨兵 | 0 号点，fa[*][0] = 0 |
| 「走 \(k\) 步到哪」 | 序列倍增，二进制拆分 |
| 「最少几步能到」 | 从大到小试跳，跳完仍不满足才跳 |
| 模板 | 位置 |
|---|---|
| 快速幂 / 矩阵快速幂 | §45.1 |
| ST 表（建 + 查） | §45.2 |
| LCA 倍增（BFS + 倍增表 + 查询） | §45.3 |
| 序列倍增（跳 \(k\) 步 / 最少步数） | §45.4 |