第 113 章 树链剖分¶
配套例题：BISHI124 【模板】最近公共祖先（LCA）、BISHI126 【模板】动态区间和Ⅱ 来源：S3 day8《树上算法》第 57–79 页（树链剖分原理与实现）；S4
模板.docx「树 → 树链剖分（两个模板）」 前置：94-树上算法、39-树状数组与线段树、45-倍增
113.0 这一章为什么存在¶
S3 day8 用了 23 页讲树链剖分，S4 的模板清单里它是「树」一节里最长的两个模板之一。 在 NOIP 复赛里，树剖是处理树上路径修改/查询的唯一通用武器。
但牛客题单里没有树剖题。最接近的是 BISHI124（纯 LCA，lowest common ancestor， 最近公共祖先：两点在树上共同的祖先里最深的那个）和 BISHI126（纯序列区间操作）—— 恰好是树剖的两个半成品：树剖 = 「树 → 序列」的映射 + 一维数据结构。
所以这一章的定位是：
| 目标 | 说明 |
|---|---|
| 补上 S3 day8 / S4 的知识缺口 | 树上路径操作的完整解法 |
| 用 BISHI124 演示剖分本身 | 树剖求 LCA 是最简单、常数最小的用法，不需要任何数据结构 |
| 用 BISHI126 演示底层结构 | 剖分之后落在哪棵一维结构上 |
| 给出诚实的可行性判断 | 树剖 + 线段树在 Python 下常数极大，\(n\) 到多少还能用？ |
先给结论（下面会展开）：
在 Python 里，「树剖 + 线段树」的实用上限大约是 \(n, q \le 3\times10^4\)。 但「树剖求 LCA」（不带数据结构）可以轻松做到 \(n, q = 5\times10^5\)。 这两者差了一个数量级半，原因就是那个 \(\log\) 和它背后的常数。
113.1 思路：把树拆成链¶
S3 day8 第 57–60 页：
树链剖分是用于处理树上路径操作的利器。 顾名思义，将树分解成一条一条的链，从而可以使用线性数据结构来处理树上路径问题。 为了方便处理，这些链都没有转折的地方，都是沿着向上的方向。某些链可能只有一个点。
第 61–62 页：
此时树上的边分为两种：一类是链内部的边，称为重边；另一类则是链外部的边，称为轻边。 处理一条树上路径的时候，通过这些链将路径切分成许多区间。
核心思想一句话：
113.2 重儿子的选法与 \(O(\log n)\) 保证¶
S3 day8 第 64–68 页：
每个节点下面只能有一条重边。通常选择这条重边的策略是根据儿子子树的大小， 选择其中大小最大的儿子，这个儿子也称为重儿子。
为什么要这么选择呢？设当前节点为 \(x\)，重儿子为 \(u\)， 显然子树大小超过 \(\frac{1}{2}size[x]\) 的儿子只能有一个， 因此除了 \(u\) 之外，其它的子树大小不超过 \(\frac{1}{2}size[x]\)。
轻边的性质非常好：从任意一个节点到根节点的路径上至多经过 \(\lceil \log n\rceil\) 条轻边。
除了最顶上的链，其余链上的区间都是因为轻边的原因而被截断的。 因此轻边的数量决定了将树上路径拆分成线性区间的数量。 根据轻边的性质，每条树上路径最多被拆分成 \(2\lceil \log n\rceil\) 个区间。
如果是树上路径加的数据结构题，再利用线段树或者树状数组就可以以单次操作 \(O(\log^2 n)\) 的时间复杂度解决了。
证明轻边数 \(\le \lceil\log n\rceil\)：每走一条轻边向上，子树大小至少翻倍 （因为轻儿子的子树大小 \(\le \frac{1}{2}\) 父亲的）， 从大小 1 翻到 \(n\) 最多 \(\log n\) 次。
这条性质就是「跳链次数是 \(\log\) 级」的全部理由，值得把因果链摆清楚：
- 按子树最大选重儿子 → 一个点的其余儿子子树都 \(\le\) 自己的一半；
- → 沿轻边向上一次，子树规模至少翻倍 → 从任一点到根最多 \(\lceil\log n\rceil\) 条轻边；
- 重链在序列上是连续的，走重链不花代价；每换一条链恰好跨一条轻边；
- → 跳链次数 = 轻边数 \(\le \lceil\log n\rceil\)，一条路径两端各跳一次，共 \(2\lceil\log n\rceil\)。
换句话说，「重儿子优先」不是为了让链变长好看，是为了让轻边变稀， 而跳链的代价只由轻边数决定。
| 量 | 上界 |
|---|---|
| 点到根的轻边数 | \(\lceil\log n\rceil\) |
| 点到根经过的链数 | \(\lceil\log n\rceil + 1\) |
| 任意两点路径拆成的区间数 | \(2\lceil\log n\rceil\) |
| 单次路径操作的复杂度 | \(O(\log n)\) 个区间 \(\times\ O(\log n)\) 每个 \(= O(\log^2 n)\) |
\(n = 5\times10^5\) 时 \(\log n \approx 19\)，一次路径操作要碰 38 个区间、 每个区间在线段树上 \(\approx 40\) 次访问 → 约 1500 次基本操作。 记住这个数字，113.7 的可行性判断全靠它。
113.3 两遍 DFS¶
S3 day8 第 70–73 页：
一般树链剖分都是两遍 DFS： 第一遍算出一些重要的信息，如子树大小
size、每个节点的父亲father、节点的深度depth等。第二遍则正式进行树链剖分。为了方便寻找区间，对每个点记录
top表示自己所处的链的顶端的节点。 为了能拆分区间，同一条链上的节点按照顺序依次编号，得到id， 这样一条链在序列上就是连续的。 DFS 的时候先找出重儿子并且优先进入。这样id实际上也是 DFS 序。
于是每个点要记 6 个数组：
| 数组 | 含义 | 第几遍算 |
|---|---|---|
par[u] |
父亲 | 第一遍 |
dep[u] |
深度 | 第一遍 |
sz[u] |
子树大小 | 第一遍 |
heavy[u] |
重儿子（无儿子则 0） | 第一遍 |
top[u] |
所在重链的顶端 | 第二遍 |
id[u] |
在序列上的位置 | 第二遍 |
id同时是 DFS 序，这是树剖的一大红利： 子树 \(u\) 恰好对应连续区间 \([id[u],\ id[u]+sz[u]-1]\)， 所以子树操作和路径操作可以用同一棵数据结构。 见 94-树上算法 的 DFS 序小节。
Python 必须写迭代 DFS¶
\(n = 5\times10^5\) 的链状树，递归深度就是 \(5\times10^5\)——必然爆 C 栈。 两遍 DFS 都要改成迭代。技巧和 112 章 一样， 但树剖有个更省事的写法：
先用一次迭代 DFS 求出「先序遍历序列」
order， 然后order逆序扫一遍算sz/heavy，正序扫一遍算dep/top/id。 三个循环全是平坦的for，一行递归都没有。
这是本章最实用的一个技巧：先序列化，再批处理。理由：
- 先序保证「父亲在儿子之前」→ 正序扫可以自顶向下传播（
dep、top）； - 逆序保证「儿子在父亲之前」→ 逆序扫可以自底向上汇总（
sz、heavy）。
113.4 模板：树链剖分（迭代版）¶
# [片段]
def hld(n, root, start, to):
"""树链剖分（三趟平坦循环，零递归）。图用 CSR (start, to) 存，点编号 1..n。
返回 (par, dep, sz, heavy, top, tid, seq)：
tid[u] —— u 在序列上的位置（1..n），同时是 DFS 序；
seq[i] —— 序列位置 i 上的点（tid 的逆），用于建初始数组；
子树 u 对应区间 [tid[u], tid[u] + sz[u] - 1]。
复杂度 O(n)。Python 下 n <= 5e5 约 2-3 秒（含建图）。
"""
# ---- 趟 1：迭代 DFS 求先序 order 与父亲 par ----
par = [0] * (n + 1) # par[root] 留 0，0 号点当哨兵，永不出现在树上
order = [0] * n # order[i] = 先序里第 i 个点（i 从 0 数）
vis = bytearray(n + 1) # 无向边存了两个方向，靠 vis 防止往父亲回走
stk = [root]
vis[root] = 1
cnt = 0
while stk:
u = stk.pop()
order[cnt] = u; cnt += 1 # 出栈顺序即先序：父亲一定早于它的所有后代
for i in range(start[u], start[u + 1]):
v = to[i]
if not vis[v]:
vis[v] = 1
par[v] = u
stk.append(v)
# ---- 趟 2：逆先序汇总 sz 与 heavy（儿子一定在父亲之后）----
sz = [0] + [1] * n # 每点自身算 1；sz[0] = 0 是给下面的比较当底
heavy = [0] * (n + 1) # 0 表示还没有重儿子（叶子就一直是 0）
for i in range(n - 1, 0, -1): # 倒着扫：处理 u 时它的子树已经全部汇总完
u = order[i] # i 从 n-1 数到 1，跳过 order[0] = root（没有父亲）
f = par[u]
sz[f] += sz[u] # 子树大小自底向上累加
if sz[u] > sz[heavy[f]]: # sz[0] = 0，heavy[f] 初值 0 天然最小
heavy[f] = u # 于是 f 的第一个儿子必定先当选，之后再择大者
# ---- 趟 3：正先序传播 dep 与 top，并按「重儿子优先」重新编号 ----
dep = [0] * (n + 1)
top = [0] * (n + 1)
tid = [0] * (n + 1) # tid[u]：u 在剖分序列上的位置，1..n
seq = [0] * (n + 1) # seq 是 tid 的逆，用来照序列顺序取初值建树
top[root] = root # 根自己是第一条重链的链顶
timer = 0
stk = [root]
while stk: # 这一趟必须重新 DFS：编号要求重儿子优先
u = stk.pop()
timer += 1 # 编号从 1 开始，和树状数组/线段树的下标习惯一致
tid[u] = timer
seq[timer] = u
h = heavy[u]
f = par[u]
tu = top[u] # 缓存下来，下面的循环里要反复用
# 先把轻儿子压栈，最后压重儿子 —— 栈是后进先出，重儿子会被最先弹出
for i in range(start[u], start[u + 1]):
v = to[i]
if v != f and v != h: # 排除父亲（无向边的回头方向）与重儿子
dep[v] = dep[u] + 1
top[v] = v # 轻儿子自成新链的顶端
stk.append(v)
if h:
dep[h] = dep[u] + 1
top[h] = tu # 重儿子继承父亲的链顶
stk.append(h) # 最后压，于是紧接着就被弹出，重链编号连续
return par, dep, sz, heavy, top, tid, seq
趟 3 的「先压轻儿子、后压重儿子」是关键。 栈后进先出，最后压的重儿子会被最先弹出， 于是重链上的点获得连续的
tid——这正是整个算法成立的前提。 写反了不会报错，只会让链在序列上碎成一段一段，复杂度退化。
113.5 路径操作：跳链¶
S3 day8 第 73–74 页：
拆分简单路径 \(u - v\) 时，如果 \(u\) 和 \(v\) 在同一条链上，那么区间的端点就是
id[u]和id[v]。如果不在同一条链上，就需要尝试跳到同一条链上。选取
top[u]和top[v]中深度较大者， 因为它不可能在另外一条深度小的链的上方。假设是top[u]，那么让 \(u\) 跳到链的顶端， 路径在链上拆分出一个区间（从 \(u\) 到top[u]），然后 \(u\) 走过一条轻边来到下一条链上。 直到出现第一种情况为止。
# [片段]
def path_ranges(u, v, top, dep, par, tid):
"""把树上路径 u-v 拆成若干个 [l, r] 区间（在剖分序列上）。
返回区间列表，共 O(log n) 个。区间之间无序，但对「区间加 / 区间和」
这类可交换的操作无所谓；对「区间赋值 + 顺序敏感」的操作需另行处理。
"""
res = []
tu, tv = top[u], top[v] # 链顶缓存，循环里每步都要读
while tu != tv: # 链顶不同 = 两点还不在同一条重链上
if dep[tu] >= dep[tv]: # ★ 跳链顶更深的那一边
res.append((tid[tu], tid[u])) # u 到本链链顶是一段连续区间（重链编号连续）
u = par[tu]; tu = top[u] # 跨一条轻边跳到上一条链，循环最多 log n 轮
else:
res.append((tid[tv], tid[v]))
v = par[tv]; tv = top[v]
# 此时 u、v 在同一条链上，LCA 就是深度较小的那个
if dep[u] <= dep[v]:
res.append((tid[u], tid[v])) # 同链上区间的左右端由深度定序，保证 l <= r
else:
res.append((tid[v], tid[u]))
return res
def lca(u, v, top, dep, par):
"""树剖求 LCA，O(log n)，**不需要任何数据结构，常数极小**。"""
tu, tv = top[u], top[v]
while tu != tv: # 和 path_ranges 同一套跳链，只是不收集区间
if dep[tu] >= dep[tv]:
u = par[tu]; tu = top[u]
else:
v = par[tv]; tv = top[v]
return u if dep[u] < dep[v] else v # 落到同一条链后，浅的那个就是 LCA
「跳链顶更深的那一边」不能写成「跳自己更深的那一边」。 反例：\(u\) 在一条很深的短链上、\(v\) 在一条起点很浅的长链上， 此时 \(dep[u] > dep[v]\) 但 \(top[u]\) 反而更浅，跳 \(u\) 会直接跳过 LCA。 判断依据必须是
dep[top[·]]。
三类操作的写法¶
| 操作 | 做法 |
|---|---|
| 路径修改/查询 | path_ranges 拆成 \(O(\log n)\) 个区间，逐个丢给数据结构 |
| 子树修改/查询 | 一个区间：\([tid[u],\ tid[u]+sz[u]-1]\) |
| 单点 | 区间 \([tid[u], tid[u]]\) |
| 边权题 | 把边权下放到深度较大的端点，路径操作时最后一段要去掉 LCA（l+1 到 r） |
边权下放后最容易忘的一步：路径 \(u\to v\) 上的边共有 \(dep[u]+dep[v]-2dep[lca]\) 条， 而点有这个数量 \(+1\) 个。所以最后那段区间要写成 \([tid[lca]+1,\ tid[\cdot]]\)， 把 LCA 本身排除掉——它代表的是 LCA 与其父亲之间的边，不在路径上。
113.6 树剖 vs 倍增 LCA¶
| 树剖 LCA | 倍增 LCA | 欧拉序 + ST 表 | |
|---|---|---|---|
| 预处理 | \(O(n)\) | \(O(n\log n)\) | \(O(n\log n)\) |
| 单次查询 | \(O(\log n)\) | \(O(\log n)\) | \(O(1)\) |
| 空间 | \(O(n)\) | \(O(n\log n)\) | \(O(n\log n)\) |
| Python 实际常数 | 最小（每次约 \(2\log n\) 次简单循环） | 中（每次 \(\log n\) 次二维索引） | 大（建表 \(n\log n\) 次） |
| 能扩展到路径操作 | ✅ | ❌（只能求 LCA 和 \(k\) 级祖先） | ❌ |
在 Python 里，树剖是 LCA 的首选： 预处理只有三趟线性扫描（无 \(\log\)），空间只有 \(O(n)\)，查询循环体极短。 \(n = 5\times10^5\) 时倍增法的
up[19][5e5]数组光建表就要 \(10^7\) 次 Python 层赋值， 而树剖的预处理只有 \(3\times5\times10^5 = 1.5\times10^6\) 次。差 6 倍以上。
113.7 Python 下的可行规模（本章最重要的一节）¶
树剖的复杂度写作 \(O(\log^2 n)\)，但常数藏在两层里：外层跳链、内层数据结构。
| 用法 | 单次操作的 Python 层迭代数（\(n=5\times10^5\)） | 可行的 \(n, q\) |
|---|---|---|
| 树剖 LCA（无数据结构） | \(\approx 2\log n \approx 38\) | \(5\times10^5\) ✅ |
| 树剖 + 树状数组（单点改 / 路径和，可减信息） | \(2\log n \times 2\log n \approx 1400\) | \(3\times10^4\) ⚠️ |
| 树剖 + 非递归线段树（路径加 / 路径和） | \(2\log n \times 6\log n \approx 4300\) | \(10^4\) ⚠️，\(3\times10^4\) 已很险 |
| 树剖 + 递归线段树 | \(\approx 10^4\) 次函数调用 | ❌ 完全不可行 |
| 子树操作（只有一个区间） | \(\approx 2\log n \approx 40\) | \(10^5\) ✅ |
估算示范：\(n = q = 10^5\)、树剖 + 非递归线段树的路径加： \(10^5 \times 4300 = 4.3\times10^8\) 次 Python 层迭代 \(\approx\) 40–60 秒。 即使牛客给「其他语言」10 秒，也差 5 倍。
诚实结论：
场景 Python 判断 只要 LCA / 只要子树操作 ✅ 放心用树剖，\(5\times10^5\) 都没问题 路径操作，\(n,q \le 10^4\) ✅ 可行 路径操作，\(n,q \le 3\times10^4\) ⚠️ 险，必须用非递归线段树或树状数组 路径操作，\(n,q \ge 10^5\) ❌ 放弃树剖，另找出路 \(n \ge 10^5\) 的路径操作题，Python 的出路是「离线」： - 只有查询没有修改 → 预处理根到点的前缀和，路径和 \(= s_u + s_v - 2s_{lca} + w_{lca}\)， 单次 \(O(\log n)\)（只花在 LCA 上），\(5\times10^5\) 可行； - 修改集中在前面、查询集中在后面 → 差分 + 一次 DFS 统计； - 树上差分：路径加 + 最后统一查，用 \(d_u{+}{=}x,\ d_v{+}{=}x,\ d_{lca}{-}{=}x,\ d_{par(lca)}{-}{=}x\)， 最后一次子树求和搞定，全程 \(O(n\log n)\) 且没有数据结构。
树上差分是 Python 选手对付「路径加 + 最后查询」的标准答案， 比树剖快一个数量级。 见 42-前缀和与差分。
113.8 例题¶
BISHI124 【模板】最近公共祖先（LCA）（中等）¶
\(N, M \le 5\times10^5\)，给定以 \(R\) 为根的树，\(M\) 次询问两点的 LCA。 时限：C/C++ 3 秒，其他语言 6 秒；空间 C/C++ 256M，其他语言 512M。 题面见 BISHI124 原题（牛客）。
ℹ️
solutions/BISHI124.py用的是另一条路线——欧拉序 + 分块稀疏表，查询 \(O(1)\)—— 已在牛客用 Python 3 通过。下面这份树剖版由scripts/verify_docs.py用官方样例实测通过，未单独提交牛客；两者的取舍见本节末尾。
这题是树剖的最佳展示场：只要剖分，不要任何数据结构。
对比三种做法在 \(n = m = 5\times10^5\) 下的开销：
| 做法 | 预处理 | 查询总量 | 空间 |
|---|---|---|---|
| 树剖 | \(3n = 1.5\times10^6\) | \(m \times 2\log n = 1.9\times10^7\) | \(O(n)\) 约 7 个数组 |
| 倍增 | \(n\log n = 10^7\) | \(m\log n = 10^7\) | \(O(n\log n)\) = \(10^7\) 个指针 ≈ 80MB |
| Tarjan 离线 | \(O(n\alpha)\) | \(O(m\alpha)\) | \(O(n+m)\) |
树剖在预处理和空间上都赢，而且倍增法的 \(10^7\) 个指针在 512M 下已经开始危险。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); root = int(data[2])
# ---- 1. CSR 邻接表 ----
deg = [0] * (n + 2) # 多开两格：下标 0 空着，n+1 放哨兵
xs = [0] * (n - 1); ys = [0] * (n - 1) # n 个点的树恰有 n-1 条边
p = 3 # 前三个 token 是 n、m、root
for i in range(n - 1):
x = int(data[p]); y = int(data[p + 1]); p += 2
xs[i] = x; ys[i] = y # 边先存起来，度数统计完才知道各自的槽位
deg[x] += 1; deg[y] += 1 # 无向边两端的度都要加
start = [0] * (n + 2)
acc = 0
for i in range(1, n + 1):
start[i] = acc # 度数的前缀和（不含自己）就是起始下标
acc += deg[i]
start[n + 1] = acc # 哨兵，让 start[u+1] 对 u = n 也成立
cur = start[:]
to = [0] * acc # acc = 2(n-1)，一次开够
for i in range(n - 1):
x = xs[i]; y = ys[i]
to[cur[x]] = y; cur[x] += 1 # 一条无向边写成两个方向
to[cur[y]] = x; cur[y] += 1
# ---- 2. 迭代 DFS：先序 order 与父亲 par ----
par = [0] * (n + 1) # par[root] 保持 0，0 号点当哨兵
order = [0] * n
vis = bytearray(n + 1) # 邻接表含回头边，靠 vis 拦住往父亲走
stk = [root]
vis[root] = 1
cnt = 0
while stk:
u = stk.pop()
order[cnt] = u; cnt += 1 # 出栈序即先序，父亲一定排在后代之前
for i in range(start[u], start[u + 1]):
v = to[i]
if not vis[v]:
vis[v] = 1
par[v] = u
stk.append(v)
# ---- 3. 逆先序：子树大小与重儿子 ----
sz = [0] + [1] * n # sz[0] = 0 是给下面的 sz[heavy[f]] 当比较底
heavy = [0] * (n + 1)
for i in range(n - 1, 0, -1): # 倒序 = 自底向上；i 停在 1，root 没有父亲
u = order[i]
f = par[u]
sz[f] += sz[u]
if sz[u] > sz[heavy[f]]: # 严格大于：同大小时保留先到的那个儿子
heavy[f] = u
# ---- 4. 正先序：深度与链顶 top（求 LCA 不需要 tid，省一趟）----
dep = [0] * (n + 1)
top = [0] * (n + 1)
top[root] = root # 根是自己所在重链的链顶
for i in range(n): # 正序 = 自顶向下，处理 u 时 top[u] 已定
u = order[i]
f = par[u]
h = heavy[u]
tu = top[u]
for j in range(start[u], start[u + 1]):
v = to[j]
if v != f: # 跳过父亲，剩下的都是儿子
dep[v] = dep[u] + 1
top[v] = tu if v == h else v # 重儿子继承链顶，轻儿子自成链顶
# ---- 5. 跳链求 LCA ----
out = []
push = out.append # 绑定成局部名字，省去每次的属性查找
for _ in range(m):
a = int(data[p]); b = int(data[p + 1]); p += 2
ta = top[a]; tb = top[b]
while ta != tb: # 链顶相同时两点已在同一条重链上，退出
if dep[ta] >= dep[tb]: # ★ 比的是 dep[top]，不是 dep 本身
a = par[ta]; ta = top[a] # 链顶更深的一方整条链都在 LCA 下方，可安全跳过
else:
b = par[tb]; tb = top[b]
push(a if dep[a] < dep[b] else b) # 同链上浅的那个即 LCA
sys.stdout.write("\n".join(map(str, out)) + "\n") # 一次性输出，逐行 print 会慢十倍
main()
样例复核（\(N=5\)，\(R=4\)，边 3-1、2-4、5-1、1-4）：
树的形状是 \(4 \to 1 \to \{3, 5\}\)、\(4 \to 2\)。
询问 \((2,4)\to4\)，\((3,2)\to4\)，\((3,5)\to1\)，\((1,2)\to4\)，\((4,5)\to4\)，
与样例输出 4 4 1 4 4 完全一致 ✓。
四个工程要点：
- 求 LCA 不需要
tid，所以第 4 趟可以直接在order上平坦地扫， 连第二次 DFS 都省了（top的传播只依赖父亲，先序保证父亲先算好）； ta = top[a]缓存下来：循环体里top[a]要读两次，缓存能省一半索引；sz[heavy[f]]依赖sz[0] = 0，所以sz必须写成[0] + [1] * n而不是[1] * (n+1)——否则每个点的第一个儿子都当不成重儿子；- \(n = 1\) 时
n - 1 = 0，xs = ys = []，所有循环自然退化，无需特判。
Python 现实性判断：
项 量级 估时 读入 \(3\times10^6\) 个 token C 层 split1.0 s 建 CSR \(\approx 3n = 1.5\times10^6\) 1.5 s 三趟扫描 \(\approx 4n = 2\times10^6\) 1.5 s \(5\times10^5\) 次查询，每次约 \(2\times19 = 38\) 次跳链 \(1.9\times10^7\) 2–4 s 输出 \(5\times10^5\) 行 join 0.3 s 总计 6–8 秒，在 6 秒限制下余量很小。 缓解因素是 \(2\log n = 38\) 次跳链只是最坏界：随机形态的树上重链很长， 实测每次询问只跳 3–5 次，只有链状/星状的极端数据才逼近上界。
稳妥的替代路线是「欧拉序 + 分块稀疏表」：预处理线性，单次查询 \(O(1)\)， 把每次询问的几十次跳链换成两次
min(切片)的 C 层扫描。solutions/BISHI124.py就是这么写的，已在牛客用 Python 3 通过。 还有一条离线路线是 Tarjan 离线 LCA（配并查集，见 38-并查集，均摊近似常数）， 代价是要把 \(5\times10^5\) 个询问全存下来再一次性回答。
BISHI126 【模板】动态区间和Ⅱ ‖ 区间修改 + 区间查询（较难）¶
\(n, q \le 5\times10^5\)，\(|a_i|, |x| \le 10^7\)。
1 l r x区间加，2 l r区间求和。 时限：C/C++ 5 秒，其他语言 10 秒；空间 C/C++ 1024M，其他语言 2048M。 题面见 BISHI126 原题（牛客）。ℹ️
solutions/BISHI126.py用的正是下面这套双树状数组，已在牛客用 Python 3 通过。 下面这份为便于讲解，初始数组用 \(n\) 次单点加建树；题解文件里换成了 \(O(n)\) 建树， 少掉约 \(1.9\times10^7\) 次循环。两份都由scripts/verify_docs.py用官方样例实测通过。
这题为什么放在树剖章：它就是树剖的底座。
把树剖的 path_ranges 拆出来的每个区间丢给它，就得到了「树上路径加 + 路径求和」。
反过来说，如果这道一维题在 Python 下都很险，那树剖版就完全没戏——
这正是 113.7 结论的实证。
题面自己给了提示：
我们可以使用线段树解决……您也可以尝试使用区间扩展版的树状数组解决本题， 其运行时的常数更小。
在 Python 里这不是「也可以」，是「必须」。用双树状数组（39 章 形态三）。
推导：设 \(d\) 是差分数组（\(d_j = a_j - a_{j-1}\)），则
所以维护两棵树：\(B_1\) 存 \(d_j\)，\(B_2\) 存 \((j-1)d_j\)。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
N = n + 1 # 多留一格，range_add 会碰 r+1
t1 = [0] * (N + 1) # 维护差分 d[j]
t2 = [0] * (N + 1) # 维护加权差分 (j-1)*d[j]
def range_add(l, r, v):
"""a[l..r] 全部 += v。差分视角：d[l] += v，d[r+1] -= v。"""
i = l; w = v * (l - 1) # 位置 l 的加权量是 (l-1)*v，配合 t2 的定义
while i <= N:
t1[i] += v; t2[i] += w; i += i & -i # i & -i 取最低位的 1，即这一格管辖的长度
i = r + 1; w = v * r # 在 r+1 处撤销，差分才只影响 [l, r]
while i <= N:
t1[i] -= v; t2[i] -= w; i += i & -i
def pre(i):
"""a[1] + ... + a[i]。★ 两棵树在同一个 while 里走，循环次数减半。"""
s1 = 0; s2 = 0; j = i
while j > 0:
s1 += t1[j]; s2 += t2[j]; j -= j & -j # 减 lowbit 逐段回退，最多 log n 步
return s1 * i - s2 # 即 i·Σd - Σ(j-1)d，正文推导的那个式子
for i in range(1, n + 1): # 初始数组视作 n 次单点加
v = int(data[1 + i]) # data[0] 是 n，data[1] 是 q，数组从下标 2 起
if v: # 跳过 0，省掉一趟树状数组
range_add(i, i, v) # 单点加就是长度为 1 的区间加
p = 2 + n # 跳过 n、q 与 n 个初值，指到第一条操作
out = []
push = out.append
for _ in range(q):
if data[p] == b"1": # 与 bytes 直接比较，比 int(...) 再判快
range_add(int(data[p + 1]), int(data[p + 2]), int(data[p + 3]))
p += 4 # 操作 1 有 4 个 token
else:
l = int(data[p + 1]); r = int(data[p + 2]); p += 3 # 操作 2 只有 3 个
push(pre(r) - pre(l - 1)) # 区间和 = 两个前缀和相减
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
Python 现实性判断：
| 项 | Python 层循环迭代数 |
|---|---|
| 初始化（\(n\) 次单点加 = 2 趟树状数组） | \(5\times10^5 \times 2\times19 \approx 1.9\times10^7\) |
| \(q\) 次修改（4 趟） | \(5\times10^5 \times 4\times19 \approx 3.8\times10^7\) |
| \(q\) 次查询（2 次双树走） | \(5\times10^5 \times 2\times19 \approx 1.9\times10^7\) |
总量约 \(7.6\times10^7\) 次，按 \(10^7\) 次/秒是 7–8 秒。10 秒限制下余量不宽裕，
但这是 Python 里唯一有希望的做法，solutions/BISHI126.py 用 \(O(n)\) 建树把第一行的
\(1.9\times10^7\) 次省掉后已通过牛客判题机。
对照非递归懒标记线段树：每次操作约 \(6\log n = 114\) 次迭代， \(10^6\) 次操作就是 \(1.1\times10^8\)——必然超时。
现在把树剖套上去看看：树上路径加 + 路径求和，每次操作要拆成 \(2\log n = 38\) 个区间，每个区间做一次上面的
range_add（\(4\times19 = 76\) 次迭代）， 单次操作 \(\approx 2900\) 次迭代。\(q = 5\times10^5\) 就是 \(1.5\times10^9\) 次—— 约 150 秒，差了 15 倍。这就是 113.7 那张表的来历：Python 的树剖路径操作，\(n,q\) 上限大约是 \(3\times10^4\)。
113.9 树剖的替代方案速查¶
拿到「树上路径操作」的题，按这个顺序考虑：
| 条件 | 方案 | Python 可行规模 |
|---|---|---|
| 只查询、不修改 | 根前缀和 + LCA | \(5\times10^5\) ✅ |
| 路径加，最后统一查 | 树上差分 + 一次子树求和 | \(5\times10^5\) ✅ |
| 单点改 + 子树查 | DFS 序 + 树状数组 | \(10^5\) ✅ |
| 子树加 + 子树查 | DFS 序 + 双树状数组 | \(10^5\) ⚠️ |
| 路径加 + 路径查，\(n\le3\times10^4\) | 树剖 + 双树状数组 | ⚠️ |
| 路径加 + 路径查，\(n\ge10^5\) | ❌ Python 放弃 | — |
| 路径最值 / 不可减信息 | 树剖 + 线段树 | \(10^4\) ⚠️ |
| 动态加边删边 | LCT（动态树） | ❌ Python 不现实 |
「树上差分」为什么这么好用：路径 \(u\to v\) 加 \(x\)，只需
最后按逆先序扫一遍把# [片段] d[u] += x # 路径两端各打一个「起点」标记 d[v] += x l = lca(u, v) d[l] -= x # LCA 被两条支路各算了一次，扣掉一次 d[par[l]] -= x # 再扣一次，挡住标记继续往 LCA 上方传；par[root] = 0，需要一个哨兵位d往上累加，每个点的值就是它被加过的总量。 全程 \(O(n + q\log n)\)，且 \(\log\) 只花在 LCA 上，没有任何数据结构。
113.10 本章速查¶
| 要点 | 结论 |
|---|---|
| 核心思想 | 树上路径 → \(O(\log n)\) 个连续区间 |
| 重儿子 | 子树最大的儿子 |
| 重边 / 轻边 | 通往重儿子 / 其他儿子 |
| 轻边性质 | 点到根最多 \(\lceil\log n\rceil\) 条轻边 |
| 路径拆成的区间数 | \(\le 2\lceil\log n\rceil\) |
| 单次路径操作 | \(O(\log^2 n)\) |
| 六个数组 | par dep sz heavy top tid |
tid |
同时是 DFS 序 → 子树是连续区间 \([tid_u, tid_u+sz_u-1]\) |
| 编号的关键 | 重儿子优先遍历（用栈时要最后压重儿子） |
| 跳链的判据 | dep[top[u]] vs dep[top[v]]，不是 dep[u] vs dep[v] |
| 边权题 | 边权下放到深端点，最后一段去掉 LCA |
| Python 实现 | 必须三趟平坦循环，零递归 |
| 三趟的分工 | 先序 order → 逆序算 sz/heavy → 正序算 dep/top/tid |
| 树剖 LCA | Python 下 LCA 的首选：\(O(n)\) 预处理、\(O(n)\) 空间 |
| 树剖 + 数据结构 | Python 上限约 \(n,q \le 3\times10^4\) |
| \(n \ge 10^5\) 的路径题 | 树上差分 / 根前缀和，别写树剖 |
| 递归线段树 + 树剖 | ❌ 绝对不可行 |
| 数据规模 → Python 现实性（树上操作） |
|---|
| 树剖求 LCA，\(n,m \le 5\times10^5\) |
| 树上差分（路径加 + 最后查），\(n \le 5\times10^5\) |
| DFS 序 + 树状数组（子树操作），\(n,q \le 10^5\) |
| 树剖 + 双树状数组（路径加/查），\(n,q \le 3\times10^4\) |
| 树剖 + 线段树，\(n,q \ge 10^5\) |
| LCT / 动态树 |