第 118 章 分治进阶：整体二分与 CDQ¶
配套例题：BISHI72 中位数之和、BISHI129 区间增量与区间小于计数 来源：S4
模板.docx/「分治」「二分」「三分」「二分答案」「整体二分」（sources/03-pascal-template/模板.md第 148–156 行的清单）；S2useful algorithm/Merge sort.cpp（归并分治） 前置：40-排序、44-二分、39-树状数组与线段树、111-偏序集与Dilworth定理
118.0 这一章为什么存在¶
S4 模板.docx 的最后一节标题是「分治」，底下列了四个条目：
前四条在 44-二分 已经讲完了。 第五条「整体二分」只有标题，正文里一行代码都没有—— 和 117 章 的「k 短路（暂时没有）」一样， 是 S4 留下的空格。
而牛客题单里同样没有整体二分 / CDQ 题。原因很直白：
| 原因 | 说明 |
|---|---|
| 这两个算法都是离线的 | 笔试题偏爱在线操作（更容易出、更容易判） |
| 都需要「把询问全部读进来重排」 | 题面要写清楚「不强制在线」，篇幅长 |
| 在 Python 里都很险 | 见 118.6 的实测：\(n=q=10^5\) 时 3 秒起步 |
那为什么要学？因为「离线 + 分治」是 Python 选手对付 \(\log^2\) 类问题的唯一出路。
39 章 给出的教学要点： 当线段树在 Python 里跑不动时，问一句「能不能不在线」。 一旦允许离线，就可以把数据结构换成排序 + 扫描， 或者把 \(O(q\log n)\) 的代价摊成 \(O(q\log q)\) 的小操作。 整体二分和 CDQ 分治就是这条路上最远的两站。
这一章的定位：
| 目标 | 说明 |
|---|---|
| 补上 S4 的「整体二分」空缺 | 原理 + 可运行的迭代模板 |
| 把分治的三种形态讲成一个体系 | 归并分治 → 整体二分 → CDQ，三者是同一个模式的三次加码 |
| 与 40 章 的逆序对、111 章 的偏序打通 | CDQ 处理的就是「三维偏序」 |
| 给出诚实的 Python 取舍 | 递归深度安全，但 merge 步骤的 Python 层循环是瓶颈；什么时候该改树状数组 |
先给结论：
分治的递归深度是 \(O(\log n)\)，所以 Python 完全不用担心爆栈—— 这是分治相对于 DFS/线段树递归的一大优势。 但每一层的 merge 都是 Python 层的逐元素循环，\(n\log n\) 次迭代。 实测：归并求逆序对 \(n=10^5\) 只要 0.16 s ✅； 整体二分 \(n=q=10^5\) 要 3.0 s ⚠️；CDQ 三维偏序 \(n=10^5\) 要 2.1 s ⚠️。 分界线在于「每层是否只有一遍线性扫描」。
118.1 分治的三步框架¶
分治（divide and conquer）永远是同样的三步：
| 步 | 名字 | 做什么 |
|---|---|---|
| 1 | 划分（divide） | 把规模 \(n\) 的问题分成若干个规模 \(n/b\) 的子问题 |
| 2 | 求解（conquer） | 递归解决子问题（规模足够小时直接算） |
| 3 | 合并（combine） | 把子问题的解拼成原问题的解 |
主定理给出复杂度：若 \(T(n) = a\,T(n/b) + f(n)\)，则
| 情形 | 结论 | 例子 |
|---|---|---|
| \(f(n) = O(n^{\log_b a - \epsilon})\) | \(T(n) = \Theta(n^{\log_b a})\) | Karatsuba 乘法（\(a=3,b=2\)） |
| \(f(n) = \Theta(n^{\log_b a})\) | \(T(n) = \Theta(n^{\log_b a}\log n)\) | 归并排序（\(a=b=2, f=n\)）→ \(n\log n\) |
| \(f(n) = \Omega(n^{\log_b a + \epsilon})\) | \(T(n) = \Theta(f(n))\) | 合并代价占主导 |
分治题的全部工夫在第 3 步「合并」。 划分几乎总是「对半砍」，求解是递归调用，只有合并需要想。 判断一道题能不能分治，就是判断「跨越中线的那部分答案，能不能在 \(O(n)\) 或 \(O(n\log n)\) 内算出来」。
分治的三个层次（本章的路线图）¶
| 层次 | 分的是什么 | 合并时算什么 | 典型问题 |
|---|---|---|---|
| 归并分治 | 下标（序列对半砍） | 「左半 × 右半」的跨中线贡献 | 逆序对、最近点对、最大子段和 |
| 整体二分 | 值域 + 询问集合 | 用一个数据结构判定每个询问该去左还是右 | 静态/动态区间第 \(k\) 小、二分答案的批处理 |
| CDQ 分治 | 时间/下标 | 「前半的修改」对「后半的询问」的影响 | 三维偏序、带修改的偏序问题 |
三者的共同点：都是「把「所有对」拆成 \(O(\log n)\) 层，每层只处理跨中线的那些对」。 差别只在「分的是什么维度」。
118.2 归并分治：从逆序对说起¶
归并排序的合并步是「两个有序段合成一个有序段」，\(O(n)\)。 它的副产品是逆序对：
归并时若从右半取走一个元素
right[j]， 说明左半剩下的len(left) - i个元素全都比它大且都在它前面， 一次性贡献这么多逆序对。
完整实现见 40-排序 · 归并的真正用途，这里只放核心一行：
# [片段]
while i < nl and j < len(right): # 两半各有一个游标，谁小谁先出队
if left[i] <= right[j]: # <= 保证稳定
res.append(left[i]); i += 1
else:
res.append(right[j]); j += 1
cnt += nl - i # ★ 左半剩余的元素都与它构成逆序对
# left[i:] 里每个都 > right[j] 且下标更靠前
归并分治的通用模式¶
任何「统计满足某条件的下标对 \((i,j)\)，\(i<j\)」的问题都可以试这个模式：
solve(l, r):
if l == r: return
mid = (l + r) // 2
solve(l, mid); solve(mid+1, r)
统计「i 在左半、j 在右半」且满足条件的对数 ← 唯一需要动脑的地方
把两半按某个键归并成有序（为上层的统计做准备）
| 问题 | 跨中线的统计 | 复杂度 |
|---|---|---|
| 逆序对 | 归并时数「左半剩余个数」 | \(O(n\log n)\) |
| 满足 \(a_i > 2a_j\) 的对数 | 双指针在两个有序段上扫 | \(O(n\log n)\) |
| 最近点对 | 按 \(x\) 分，只检查中线两侧 \(\pm d\) 条带内按 \(y\) 排序的相邻 7 个点 | \(O(n\log n)\) |
| 最大子段和 | 跨中线的最大和 = 左半后缀最大 + 右半前缀最大 | \(O(n\log n)\)（不如 DP 的 \(O(n)\)） |
| 区间 \([l,r]\) 内值在 \([x,y]\) 的个数（离线） | 归并 + bisect |
\(O(n\log^2 n)\) |
归并分治 vs 树状数组：这两者能解决的问题高度重叠。 逆序对既能归并分治也能「离散化 + 树状数组倒序扫」， 因为两者本质上都是「把二维偏序拆成一维扫描 + 一维数据结构」。 实测两者在 \(n=10^5\) 时都是 0.16 s，打成平手（见 118.6）。
选择依据： - 值域好离散化、只统计「个数」→ 树状数组（代码短、无递归）； - 需要在合并时做复杂的双指针/
bisect逻辑 → 归并分治； - 需要「按时间分治」（带修改）→ 只能 CDQ。
118.3 整体二分¶
问题背景¶
单个询问「区间 \([l,r]\) 的第 \(k\) 小」怎么做？
每次判定需要「区间内 \(\le v\) 的个数」，用树状数组要 \(O(\log n)\)， 所以单个询问是 \(O(\log V\log n)\)，\(q\) 个询问是 \(O(q\log V\log n)\)。
问题出在哪：每个询问独立二分，每次判定都要重新往树状数组里塞元素再撤掉， 这部分工作被重复了 \(q\) 遍。
核心思想：把 \(q\) 个二分「同时」做¶
整体二分（parallel binary search）= 把所有询问的二分过程按层同步推进。 在值域的第 \(d\) 层，所有还在这一层的询问共享同一次「把元素塞进数据结构」的操作。
先跨过一层观念转换：询问也是被分治的数据。 平时写二分，被分的是「值域」，询问只是站在外面下达指令的一方。 整体二分把询问降格成和数组元素同等地位的对象： 每一层递归都拿着两袋东西——一袋元素、一袋询问——同时切成两半往下传。 元素按「值 \(\le v_m\) 还是 \(> v_m\)」分，询问按「答案在左半值域还是右半」分。 递归树的每个节点因此都是一个「小规模的同类问题」， 这正是分治能成立的原因，也是理解整体二分唯一的门槛。
CDQ 的转换更彻底：修改和询问被混进同一条按时间排的序列， 然后按下标对半砍。看懂这一步，后面的代码都只是归并而已。
| 单独二分 | 整体二分 | |
|---|---|---|
| 递归的对象 | 一个询问 | （值域区间, 元素集合, 询问集合） 三元组 |
| 层数 | \(\log V\) | \(\log V\) |
| 每层的数据结构操作 | \(q \times\)（塞 + 撤） | \(n\) 次塞 + \(n\) 次撤（整层共享） |
| 总复杂度 | \(O(q\log V\log n)\) | \(O((n+q)\log V\log n)\) |
当 \(q \gg 1\) 时整体二分把「\(q\) 倍的塞元素代价」压成了「1 倍」。
算法¶
solve(值域区间 [vl, vr], 元素集合 E, 询问集合 Q):
if Q 为空: return
if vl == vr: 所有 Q 中的询问答案都是 vl，return
vm = (vl + vr) // 2
把 E 中值 <= vm 的元素塞进树状数组
for 每个询问 q in Q:
c = 树状数组查 q 的区间和 ← 「区间内值 <= vm 的个数」
if c >= q.k: q 归入左半 QL
else: q.k -= c，归入右半 QR ← ★ k 要减掉
把刚塞进去的元素全部撤掉 ← ★ 必须撤，否则污染兄弟分支
solve([vl, vm], E 中值 <= vm 的部分, QL)
solve([vm+1, vr], E 中值 > vm 的部分, QR)
两个必须记牢的细节：
| 细节 | 为什么 |
|---|---|
归入右半时 k -= c |
右半的询问已经确定「左半贡献了 \(c\) 个」，剩下要找的是第 \(k-c\) 小 |
| 每层结束必须撤销树状数组 | 递归到兄弟分支时数据结构必须是干净的。忘了撤是整体二分第一大 bug |
模板（迭代版，静态区间第 \(k\) 小）¶
数组静态时，「值 \(\le v_m\) 的元素」在「按值排好序的元素列表」里恰好是一段前缀，
于是元素集合可以用下标区间 [ilo, ihi] 表示，不需要真的拆列表。
# [片段]
def kth_offline(a, queries):
"""整体二分求**静态**区间第 k 小。
a —— 0-indexed 数组
queries —— [(l, r, k)]，0-indexed 闭区间，k 从 1 开始；★ 会被就地修改（k 递减）
返回每个询问的答案。
复杂度 O((n + q) log V log n)。
★ 用显式栈而不是递归：层数只有 log V，递归也安全，但迭代少一层函数调用开销。
"""
n = len(a)
q = len(queries)
vals = sorted(set(a)) # 离散化后的值域
ans = [0] * q
bit = [0] * (n + 1) # 树状数组：下标 i 处放 1 表示「该位置的值已入库」
def add(i, v): # 下标 i（0-indexed）处 += v
i += 1 # 树状数组从 1 计数，0 号位是 lowbit 的死循环点
while i <= n:
bit[i] += v
i += i & -i # 逐级上传给管辖自己的父格
def pre(i): # 下标 [0, i] 的和
i += 1
s = 0
while i > 0:
s += bit[i]
i -= i & -i # 减 lowbit 逐段回退，最多 log n 步
return s
items = sorted(range(n), key=lambda i: a[i]) # 按值排序的下标 —— 全局只排一次
# 栈里的五元组 = (值域左端, 值域右端, 元素段左端, 元素段右端, 询问编号表)
stack = [(0, len(vals) - 1, 0, n - 1, list(range(q)))]
while stack:
vl, vr, ilo, ihi, qs = stack.pop()
if not qs:
continue # 没有询问落到这个分支，整棵子树都不用展开
if vl == vr: # 值域收缩到一个点 -> 定答案
v = vals[vl]
for j in qs:
ans[j] = v
continue
vm = (vl + vr) // 2
# ---- 把值 <= vals[vm] 的元素塞进树状数组（它们在 items 里是一段前缀）----
added = []
p = ilo
while p <= ihi and a[items[p]] <= vals[vm]:
add(items[p], 1) # 按「原下标」入库，这样才能按区间查
added.append(items[p])
p += 1 # 循环结束时 p 是左右两段元素的分界
# ---- 分流询问 ----
left = []
right = []
for j in qs:
l, r, k = queries[j]
c = pre(r) - (pre(l - 1) if l > 0 else 0) # [l, r] 里值 <= vals[vm] 的个数
if c >= k: # 小值够多，第 k 小就藏在左半值域
left.append(j)
else:
queries[j] = (l, r, k - c) # ★ k 要减掉左半的贡献
right.append(j) # 右半只需再找第 k-c 小
# ---- 撤销：递归到兄弟分支前数据结构必须干净 ----
for i in added:
add(i, -1) # 只撤自己加过的，比整棵树清零快得多
stack.append((vl, vm, ilo, p - 1, left)) # 左分支拿前缀那段元素
stack.append((vm + 1, vr, p, ihi, right)) # 右分支拿剩下那段
return ans
自测（与 sorted(a[l:r+1])[k-1] 暴力对拍 300 组随机小数据，全部一致）。
带修改的版本¶
数组会被单点修改时，元素集合不再是「按值排序的一段前缀」， 必须真的维护一个操作序列：
| 操作类型 | 在整体二分里的行为 |
|---|---|
| 插入值 \(v\) 到位置 \(p\) | 若 \(v \le v_m\) 则塞进树状数组，归入左半；否则归入右半 |
| 删除位置 \(p\) 的值 \(v\) | 同上，但塞的是 \(-1\) |
| 询问 \((l,r,k)\) | 查区间和 \(c\)，按 \(c\) 与 \(k\) 分流 |
「单点修改」拆成「删旧值 + 插新值」两个操作， 于是带修区间第 \(k\) 小（洛谷 P2617）就和静态版共用同一份框架。 复杂度 \(O((n+q)\log V\log n)\)，和主席树 + 树套树同阶但常数小得多—— 这是整体二分在 C++ 里最大的卖点。
整体二分的适用信号¶
| 信号 | 说明 |
|---|---|
| 多个询问，每个都可以独立二分答案 | 这是前提 |
| 判定函数需要一个数据结构，且「加入元素」的代价可以被多个询问共享 | 这是收益来源 |
| 不强制在线 | 硬性要求 |
| 判定关于二分的量单调 | 与普通二分同一个要求 |
⚠️ 反例：可行性不单调就不能整体二分。 比如 BISHI91 拼接木棍（44-二分 的反例题）—— 可行性关于 \(L\) 不单调（需 \(L \mid T\)），连普通二分都不能用，整体二分更无从谈起。 整体二分只是把「多个二分」批处理，它不能让不能二分的东西变得能二分。
118.4 CDQ 分治¶
从「二维偏序」到「三维偏序」¶
111 章 建立了偏序的语言。回顾一下维数的递进：
| 维数 | 问题 | 做法 |
|---|---|---|
| 一维 | 排序 | sort |
| 二维 | 逆序对 / LIS / 二维数点 | 一维排序 + 一维数据结构（树状数组） |
| 三维 | 三维偏序：对每个 \(i\) 求 \(\lvert\{j: a_j\le a_i, b_j\le b_i, c_j\le c_i\}\rvert\) | 一维排序 + 一维 CDQ + 一维数据结构 |
| 四维 | — | CDQ 套 CDQ，或 K-D 树 / bitset 暴力 |
三维偏序的标准三段式：
CDQ 的本质：让「前半」影响「后半」¶
cdq(l, r):
if l == r: return
mid = (l + r) // 2
cdq(l, mid) ← 先递归，保证左半内部已算完
cdq(mid+1, r)
统计「左半的元素」对「右半的元素」的贡献 ← 唯一动脑的地方
按第二维把两半归并（为上层准备）
为什么这样能不重不漏：任意一对 \((j, i)\) 且 \(j < i\)（第一维已有序）， 在递归树上恰好有一层让 \(j\) 落在左半、\(i\) 落在右半。 所以每一对被统计恰好一次。
这是 CDQ 与归并分治的唯一区别： - 归并分治统计的是「对称的贡献」（逆序对：左半元素与右半元素互相构成逆序对）； - CDQ 统计的是「单向的贡献」（左半的「修改」影响右半的「询问」，反之不影响）。
所以 CDQ 又被叫作「按时间分治」——第一维通常就是时间/操作序号。
模板：三维偏序¶
# [片段]
def cdq3d(pts, K):
"""三维偏序（洛谷 P3810 陌上花开）。
pts —— [(a, b, c)] 列表；K —— c 的值域上界
返回 cnt，cnt[d] = 「f 值恰为 d」的元素个数，
其中 f(i) = |{j != i : a_j<=a_i, b_j<=b_i, c_j<=c_i}|。
三段式：a 排序 -> b 用 CDQ -> c 用树状数组。
★ 完全相同的三元组必须**合并去重**，否则它们之间会互相少算。
复杂度 O(n log^2 n)。
"""
n = len(pts)
pts = sorted(pts) # 第一维 a：排序消掉
uniq = [] # 去重，w 记重数
w = []
for p in pts:
if uniq and uniq[-1] == p: # 排好序后相同三元组必然相邻，一次扫描即可去重
w[-1] += 1
else:
uniq.append(p)
w.append(1)
m = len(uniq)
f = [0] * m # f[i]：严格来自「别的三元组」的支配计数
bit = [0] * (K + 1) # 树状数组按 c 的值建，所以开到值域上界 K
def add(i, v): # 第三维 c：树状数组
while i <= K:
bit[i] += v
i += i & -i
def pre(i):
s = 0
while i > 0: # 前缀和 = 已入库元素里 c 值 <= i 的个数
s += bit[i]
i -= i & -i
return s
def solve(lo, hi, ids):
"""ids 是 [lo, hi] 内元素的 id 列表，按 a 序（即 id 升序）传入，
返回按 b 排好序的 id 列表。"""
if lo == hi:
return [ids[0]] # 单个元素天然有序，且自己不会支配自己
mid = (lo + hi) // 2
L = solve(lo, mid, ids[:mid - lo + 1]) # 递归后 L 已按 b 有序
R = solve(mid + 1, hi, ids[mid - lo + 1:]) # R 同理；两半内部的贡献已算完
# ---- 归并：b 小的先处理；左半元素「入库」，右半元素「查询」 ----
res = []
touched = [] # 记下本层入过库的元素，末尾要撤
i = j = 0
while i < len(L) and j < len(R):
if uniq[L[i]][1] <= uniq[R[j]][1]: # <= ：b 相等也满足偏序，左边要先入库
add(uniq[L[i]][2], w[L[i]]) # 左半 -> 入库
touched.append(L[i])
res.append(L[i]); i += 1
else:
f[R[j]] += pre(uniq[R[j]][2]) # 右半 -> 查库
res.append(R[j]); j += 1 # 库里此刻恰是 a 更小、b 不更大的那些
while i < len(L):
res.append(L[i]); i += 1 # 右半查完了，左半剩的只需并进结果
while j < len(R):
f[R[j]] += pre(uniq[R[j]][2]) # ★ 左半已全部入库，右半剩余也要查
res.append(R[j]); j += 1
for x in touched: # ★ 撤销，别污染兄弟分支
add(uniq[x][2], -w[x])
return res # 返回按 b 有序的合并结果，供上一层用
solve(0, m - 1, list(range(m)))
cnt = [0] * n
for i in range(m):
cnt[f[i] + w[i] - 1] += w[i] # 同值元素互相计入，故 +w-1
return cnt
自测（与 \(O(n^2)\) 暴力对拍 300 组随机小数据，全部一致）。
三个坑： 1. 完全相同的三元组必须去重合并。若 \((1,1,1)\) 出现 3 次， CDQ 只会让先出现的贡献给后出现的，导致答案偏小。 去重后用
w（重数）参与计算，最后f[i] + w[i] - 1补回来； 2. 归并的比较必须是<=而不是<。\(b\) 相等时也算「满足偏序」， 所以左半的相等元素要先入库，才能被右半查到； 3.touched必须撤销。和整体二分一样，兄弟分支要看到干净的数据结构。 「只撤销自己加过的」比「整棵树清零」快得多。
CDQ 的另一个大用途：动态问题静态化¶
「带修改的二维数点」是 CDQ 最常见的形态：
| 维度 | 内容 |
|---|---|
| 第一维 | 时间（操作序号）—— 天然有序，不用排 |
| 第二维 | 位置 —— CDQ 归并 |
| 第三维 | 值 —— 树状数组 |
CDQ 分治 = 用「分治」代替「一个维度的数据结构」。 树套树是「数据结构套数据结构」（\(O(\log^2 n)\)，常数巨大、空间大）； CDQ 是「分治套数据结构」（同样 \(O(\log^2 n)\)，但常数小、空间 \(O(n)\)）。 在 C++ 里这是压倒性优势；在 Python 里……见下节。
118.5 Python 的取舍¶
好消息：递归深度是安全的¶
| 算法 | 递归深度 | Python 判断 |
|---|---|---|
| DFS（链状图） | \(O(n)\) | ❌ 必须改迭代（60 章） |
| 递归线段树 | \(O(\log n)\)，但每次操作都递归 | ⚠️ 函数调用开销致命（39 章） |
| 归并分治 / CDQ / 整体二分 | \(O(\log n) \approx 17\) | ✅ 完全安全，不用 setrecursionlimit |
关键差别：线段树是「\(q\) 次操作 × 每次 \(O(\log n)\) 层递归」= \(q\log n\) 次函数调用； 分治是「一共 \(O(n)\) 次函数调用，每次做 \(O(\text{段长})\) 的工作」。 分治把函数调用开销摊薄了，这是它在 Python 里比递归线段树好得多的根本原因。
坏消息：merge 步骤是纯 Python 层循环¶
| 算法 | 每层的工作 | 总迭代数 |
|---|---|---|
| 归并求逆序对 | 一遍线性归并 | \(n\log n \approx 1.7\times10^6\)（\(n=10^5\)） |
| 整体二分 | 一遍元素塞入 + \(q\) 次树状数组查询 | \((n + 2q\log n)\log V \approx 1.2\times10^8\) |
| CDQ 三维偏序 | 一遍归并 + 每个元素一次树状数组操作 | \(n\log n\log V \approx 3.5\times10^7\) |
多出来的那个 \(\log\)（来自树状数组）就是分水岭。
实测数据（\(n = q = 10^5\)）¶
| 算法 | 实测耗时 | 判断 |
|---|---|---|
| 归并分治求逆序对 | 0.16 s | ✅ 稳 |
| 树状数组 + 离散化求逆序对 | 0.16 s | ✅ 打成平手 |
| CDQ 三维偏序（\(c\) 值域 \(2\times10^5\)） | 2.1 s | ⚠️ 险 |
| 整体二分（静态区间第 \(k\) 小） | 3.0 s | ⚠️ 险 |
| 树套树（线段树套线段树） | \(10^8\) 量级 | ❌ 完全不可行 |
| 主席树（可持久化线段树） | 建树 \(n\log n\) 个节点 = \(1.7\times10^6\) 个 Python 对象/数组格 | ❌ 内存与常数双杀 |
诚实结论：
场景 Python 判断 只需要「统计满足偏序的对数」（二维） ✅ 用树状数组，不要写分治 三维偏序，\(n \le 10^5\)，时限 \(\ge\) 5 秒 ⚠️ CDQ 可以试，2 秒左右 三维偏序，\(n \le 10^5\)，时限 2 秒 ❌ 区间第 \(k\) 小（静态），\(n=q\le10^5\)，时限 \(\ge\) 5 秒 ⚠️ 整体二分 3 秒 区间第 \(k\) 小（静态），可以离线且值域小 ✅ 改「分块 + 块内排序副本 + bisect」，见 116 章带修区间第 \(k\) 小，\(n=q\ge10^5\) ❌ Python 放弃 任何需要主席树 / 树套树的题 ❌
什么时候该把分治换成树状数组离线¶
判断标准：需要「跨中线的复杂逻辑」吗？
| 需求 | 用什么 | 理由 |
|---|---|---|
| 统计二维偏序对数 | 树状数组 + 排序 | 一遍扫描，没有递归、没有切片 |
| 离线区间查询（莫队式） | 排序 + 扫描 + 树状数组 | 同上 |
| 三维偏序 | CDQ（没有更好的选择） | 树状数组只能管一维 |
| 带修 + 多维 | CDQ | 分治是唯一能「消掉时间维」的手段 |
归并时要做 bisect / 双指针 |
归并分治 | 树状数组表达不了 |
Python 的通用降级路线（按优先级）：
树套树 / 主席树 ❌ ↓ 降级 CDQ 分治 / 整体二分 ⚠️ 3 秒量级 ↓ 降级 分块 + 块内排序副本 + bisect ⚠️ 但常数全在 C 层 ↓ 降级 排序 + 树状数组（若能把维数降到 2） ✅ ↓ 降级 Counter / sorted / bisect 一遍扫 ✅ 最优每往下一级，都是把 Python 层循环换成 C 层操作。 这条链条是整个第十部分反复出现的主题。
三个实现层面的 Python 优化¶
| 优化 | 效果 |
|---|---|
ids[:mid-lo+1] 的切片 → 改成传 (lo, hi) 下标 + 全局数组 |
省掉 \(O(n\log n)\) 次列表分配 |
归并用 res.append → 预分配 res = [0]*len + 下标赋值 |
快 10–20% |
树状数组的 add/pre 内联进归并循环 |
省掉 \(n\log n\) 次函数调用，能快 30% |
| 整体二分的递归 → 显式栈 | 层数只有 17，收益有限，但少一层开销 |
118.6 例题¶
BISHI72 中位数之和（较难）¶
给定长度 \(n\) 的二进制数组 \(a\)（元素为 0 或 1），\(k\) 为奇数。 求 \(a\) 的所有长度恰为 \(k\) 的子序列的中位数之和，对 \(P = 10^9+7\) 取模。 \(t \le 10^4\) 组，\(\sum n \le 2\times10^5\)。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 BISHI72 原题（牛客）。
✅ 题解见
solutions/BISHI72.py，已通过官方样例验证。
这题为什么放在分治章：因为它是一道「看着像分治，实际不用分治」的题， 而分辨这一点的能力比会写 CDQ 更值钱。
为什么会想到分治：「所有子序列的某个统计量之和」这种句式， 在很多题里确实要靠分治（比如「所有子区间的最大值之和」用单调栈或分治）。 而且「中位数」天然带着「排序 / 第 \(k\) 小」的味道，容易联想到整体二分。
为什么分治在这里是错的路：
| 尝试 | 问题 |
|---|---|
| 枚举子序列 | \(\binom{n}{k}\) 是天文数字 |
| 分治：按下标对半，统计跨中线的子序列 | 子序列不要求连续，「跨中线」不构成有意义的划分 |
| 整体二分：二分中位数的值 | 中位数只能是 0 或 1，值域只有两个点，二分毫无意义 |
| 0/1 转化 + 组合计数 | ✅ 正解 |
关键观察（两步）：
第一步：0/1 值下「求和 = 计数」。 中位数只能是 0 或 1，所以
第二步：中位数为 1 的判据。 长度 \(k\)（奇数）的 0/1 序列，排序后第 \(h = \frac{k+1}{2}\) 个是 1 \(\iff\) 序列里 1 的个数 \(\ge h\)。
于是设数组里有 \(c_1\) 个 1、\(c_0 = n - c_1\) 个 0：
（从 1 里挑 \(j\) 个、从 0 里挑 \(k-j\) 个；按位置计数，同值元素在不同下标算不同子序列，正合题意。）
验算样例：\(n=5, k=1\)，全是 1 → \(c_1=5, c_0=0, h=1\)，\(j=1\)： \(\binom{5}{1}\binom{0}{0} = 5\) ✓
import sys
P = 1000000007
def main() -> None:
data = sys.stdin.buffer.read().split()
t = int(data[0])
idx = 1 # 游标：t 之后紧接着是第一组数据
cases = [] # 先把所有组读完，才知道阶乘表要开多大
mx = 1 # 所有组里最大的 n
for _ in range(t):
n = int(data[idx]); k = int(data[idx + 1]); idx += 2
c1 = 0 # 本组里 1 的个数，数组本身不必存下来
for j in range(idx, idx + n):
if data[j] == b"1": # 与 bytes 直接比，省去 int() 转换
c1 += 1
idx += n
cases.append((n, k, c1))
if n > mx:
mx = n
fact = [1] * (mx + 1) # ★ 全局只建一次阶乘表
for i in range(2, mx + 1): # 从 2 起：0! 和 1! 都是 1，初值已对
fact[i] = fact[i - 1] * i % P
inv_fact = [1] * (mx + 1)
inv_fact[mx] = pow(fact[mx], P - 2, P) # 费马小定理求一次逆元
for i in range(mx, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % P # 再线性递推出全部逆阶乘
# 由 1/(i-1)! = (1/i!) * i，倒着推只花 O(n) 次乘法
def C(a: int, b: int) -> int:
if b < 0 or b > a:
return 0 # 越界统一返回 0，省掉一堆边界判断
return fact[a] * inv_fact[b] % P * inv_fact[a - b] % P
out = []
for n, k, c1 in cases:
c0 = n - c1 # 0 的个数
h = (k + 1) // 2 # 至少要有 h 个 1，中位数才是 1
s = 0
for j in range(h, min(k, c1) + 1): # j = 选中的 1 的个数，上界受 k 和 c1 双重限制
s += C(c1, j) * C(c0, k - j) % P # 从 1 里选 j 个、从 0 里选 k-j 个
out.append(str(s % P)) # 循环内不取模也行，最后统一归约一次
sys.stdout.write("\n".join(out) + "\n")
main()
复杂度：预处理 \(O(\max n)\) + 每组 \(O(k)\)，总 \(O(\max n + \sum n)\)。 注意这是线性的——比任何分治做法都好。
四个坑（来自题解记录）：
- 逐组重建阶乘表会退化成 \(O(t\cdot n)\)，\(t=10^4\) 时直接爆。 必须在最外层建一次表，表长取所有测试用例里最大的 \(n\)； → 所以要先把所有输入读完（本身就是一次「离线」！）；
- 求和上界是 \(\min(k, c_1)\)，下界还要满足 \(k-j \le c_0\) 即 \(j \ge k-c_0\)—— 统一用 \(\binom{x}{y}=0\ (y>x \text{ 或 } y<0)\) 兜住最省心；
- 中位数是排序后第 \(\frac{k+1}{2}\) 个（1-indexed），\(k\) 奇数时 \(h = (k+1)//2\)；
- 每组 \(n\) 可能很小但 \(t\) 很大，IO 必须整块读。
本题给出的判断口诀： 看到「所有子序列/子集的某统计量之和」，先问「值域有多小」。 值域只有 \(\{0,1\}\) 时，「求和」退化成「计数」， 而计数往往有闭形式的组合公式，比任何分治都快一个数量级。
这与 116 章 的「先看值域再选数据结构」是同一条原则： 值域是解题时最该先找的那个数。
组合数取模的完整技术见 84-组合数学。
BISHI129 区间增量与区间小于计数（中等）¶
\(n, q \le 10^5\)，\(|a_i| \le 10^7\)。
1 l r x：区间加；2 l r x：查询 \([l,r]\) 内 \(< x\) 的元素个数（\(|x| \le 10^9\)）。 时限：C/C++ 5 秒，其他语言 10 秒。 题面见 BISHI129 原题（牛客）。✅ 题解见
solutions/BISHI129.py，已通过官方样例验证。 完整代码与讲解在 116-平衡树与有序集合（分块 + 块内排序副本） 与 39-树状数组与线段树（分块视角）。 这里只回答一个问题：为什么整体二分 / CDQ 在这题用不上？
这题长得非常像整体二分的模板题：多个询问、每个都涉及「值的比较」、 而且允许离线。但三条路都堵死了：
| 尝试 | 为什么不行 |
|---|---|
| 整体二分（二分 \(x\)） | 询问给的 \(x\) 是固定的，不需要二分——我们要的不是「第 \(k\) 小是多少」，而是「\(< x\) 的有几个」。没有需要二分的未知量 |
| 整体二分（二分值域，把询问分流） | 分流的判据是「区间内 \(\le v_m\) 的个数与 \(k\) 比较」，本题没有 \(k\)；改成直接统计的话，就退化成「对每个询问在值域上跑一遍」= \(O(q\log V\log n)\)，比分块还慢 |
| CDQ 按时间分治 | 修改是区间加，它把区间内所有元素的值同时平移。CDQ 要求「前半的修改对后半询问的贡献可以用一维数据结构统计」，而「区间加」改变的是值这一维本身，无法在树状数组上表达 |
| 树套树 | \(O(\log^2 n)\)，Python \(10^8\) 量级 ❌ |
| 分块 + 块内排序副本 | ✅ 正解 |
根因：「区间加」是一个会破坏值域有序性的操作。
| 修改类型 | 对「值域数据结构」的影响 | 能否离线分治 |
|---|---|---|
| 单点赋值 / 单点加 | 只动一个元素 → 拆成「删旧值 + 插新值」 | ✅ CDQ / 整体二分都行 |
| 区间加 | 动 \(O(r-l)\) 个元素的值 | ❌ 拆不开 |
| 区间赋值 | 同上 | ❌ |
而分块之所以能救命，正是因为它找到了一个局部不变量：
整块加法只是「整体平移」，不改变块内元素的相对顺序。 于是块内的排序副本可以完全不动，只记一个偏移量
off[b]， 查询时把阈值反向平移成 \(x - \text{off}[b]\) 即可。
| 结构 | 每次操作的代价 | Python 层 vs C 层 |
|---|---|---|
| 整体二分 | \(O(\log V\log n) \approx 350\) 次迭代 | 全在 Python 层 |
| CDQ | 同阶 | 全在 Python 层 |
分块 + bisect |
\(O(\sqrt n)\) 次 bisect + \(O(\sqrt n)\) 次 C 层比较 |
约 250 次 C 层调用 |
这就是本章最重要的取舍结论： 在 Python 里，\(O(\sqrt n)\) 的 C 层操作常常打得过 \(O(\log^2 n)\) 的 Python 层操作。 \(n = 10^5\) 时 \(\sqrt n = 316\)、\(\log^2 n = 289\)——两者数量级相同， 而「C 层 250 次」和「Python 层 350 次」相差 5–20 倍。
所以拿到「离线 + 多维」的题，Python 选手的第一选择是分块，第二选择才是 CDQ。 这条结论与 39 章 「分块在 Python 里的特殊地位」完全一致。
想练手整体二分与 CDQ 的话¶
| 想练 | 推荐题 | Python 可行性 |
|---|---|---|
| 归并分治求逆序对 | 洛谷 P1908 逆序对 | ✅ 树状数组也一样快 |
| 最近点对（归并分治） | 洛谷 P1429 平面最近点对 | ✅ \(n\le10^5\) |
| 三维偏序（CDQ） | 洛谷 P3810 陌上花开 | ⚠️ 2 秒左右，时限 1 秒则不行 |
| 整体二分（静态第 \(k\) 小） | 洛谷 P3834【模板】可持久化线段树 2 | ⚠️ 3 秒 |
| 带修区间第 \(k\) 小 | 洛谷 P2617 Dynamic Rankings | ❌ Python 无解 |
| CDQ 优化 DP | 洛谷 P4093 [HEOI2016] 序列 | ❌ |
| 分块替代方案 | 洛谷 P2801 教主的魔法 | ✅ 首选 |
118.7 本章速查¶
| 要点 | 结论 |
|---|---|
| 分治三步 | 划分 → 求解 → 合并 |
| 分治题的全部工夫 | 在「合并」这一步（划分几乎总是对半砍） |
| 判断能不能分治 | 「跨中线的贡献能不能在 \(O(n)\) / \(O(n\log n)\) 算出来」 |
| 主定理（\(a=b=2, f=n\)） | \(T(n)=\Theta(n\log n)\) |
| 归并求逆序对的一行 | 从右半取元素时 cnt += nl - i |
| 稳定性的关键 | 归并比较用 <= 而不是 < |
| 归并分治的通用模式 | 递归两半 → 统计跨中线的对 → 按键归并 |
| 归并分治 vs 树状数组 | 二维偏序两者等价，\(n=10^5\) 都是 0.16 s；优先树状数组（无递归、无切片） |
| 整体二分是什么 | 把 \(q\) 个独立的二分按层同步推进，共享「塞元素」的代价 |
| 整体二分的递归对象 | （值域区间, 元素集合, 询问集合） |
| 整体二分复杂度 | \(O((n+q)\log V\log n)\) |
| 整体二分坑一 | 归入右半时 k -= c |
| 整体二分坑二 | 每层结束必须撤销数据结构（第一大 bug） |
| 静态数组的简化 | 「值 \(\le v_m\) 的元素」在按值排序的列表里是一段前缀 → 用下标区间表示 |
| 带修版怎么做 | 「单点修改」拆成「删旧值 + 插新值」两个操作 |
| 整体二分的前提 | 多个询问 + 判定单调 + 不强制在线 |
| 整体二分不能做什么 | 不能让不能二分的东西变能二分（如 BISHI91） |
| CDQ 是什么 | 用分治代替「一个维度的数据结构」 |
| CDQ 的三段式 | 第一维排序 → 第二维 CDQ → 第三维树状数组 |
| CDQ 不重不漏的原因 | 任一对 \((j,i)\) 恰好有一层让 \(j\) 在左半、\(i\) 在右半 |
| CDQ vs 归并分治 | 归并统计对称贡献；CDQ 统计单向贡献（前半修改 → 后半询问） |
| CDQ 的别名 | 按时间分治 |
| 三维偏序坑一 | 完全相同的三元组必须去重合并，用重数 w 补回 |
| 三维偏序坑二 | 归并比较用 <=（\(b\) 相等也满足偏序） |
| 三维偏序坑三 | touched 必须撤销（只撤自己加过的，别整树清零） |
| CDQ vs 树套树 | 同为 \(O(\log^2 n)\)，但 CDQ 常数小、空间 \(O(n)\) |
| 分治的递归深度 | \(O(\log n)\approx17\)，Python 完全安全 |
| 分治 vs 递归线段树 | 分治总共 \(O(n)\) 次函数调用；线段树是 \(q\log n\) 次 → 分治摊薄了调用开销 |
| 分治在 Python 的瓶颈 | merge 步骤的 Python 层逐元素循环 |
| 分水岭 | 每层只有一遍线性扫描（✅）vs 每层还多一个 \(\log\)（⚠️） |
| Python 降级路线 | 树套树/主席树 ❌ → CDQ/整体二分 ⚠️ → 分块 + bisect → 排序 + 树状数组 ✅ → 一遍扫 ✅ |
| 最重要的取舍结论 | \(O(\sqrt n)\) 的 C 层操作常常打得过 \(O(\log^2 n)\) 的 Python 层操作 |
| 「区间加」为什么毁掉离线分治 | 它同时改变 \(O(r-l)\) 个元素的值，拆不成单点操作 |
| 分块为什么能救 BISHI129 | 整块加只是整体平移，不改变块内相对顺序 |
| BISHI72 的口诀 | 「所有子序列的统计量之和」→ 先看值域；值域 \(\{0,1\}\) 时求和 = 计数 = 组合公式 |
| 数据规模 → Python 现实性（本章算法） |
|---|
| 归并分治求逆序对，\(n\le10^5\) |
| 归并分治求逆序对，\(n\le10^6\) |
| 树状数组 + 离散化求逆序对，\(n\le10^5\) |
| 最近点对（归并分治），\(n\le10^5\) |
| CDQ 三维偏序，\(n\le10^5\) |
| 整体二分（静态区间第 \(k\) 小），\(n=q\le10^5\) |
| 整体二分，\(n=q\le10^4\) |
| 带修区间第 \(k\) 小，\(n=q\ge10^5\) |
| 树套树（线段树套线段树），\(n\ge10^5\) |
| 主席树，\(n\ge10^5\) |
| 分块 + 块内排序副本，\(n=q\le10^5\) |
| BISHI72 组合计数，\(\sum n\le2\times10^5\) |