分治不是“把递归写得更复杂”，而是利用问题的结构：大实例可以由几个相对独立的小实例组成。设计时先把三阶段写在纸上，再决定函数参数和代码。

什么问题适合分治

通常要同时观察三点：

1. 可分解：能把问题拆成规模显著更小的同类问题；
2. 子问题近似独立：子问题之间没有大量重复状态，也不需要频繁交换信息；
3. 可合并：子问题答案能在可接受成本内恢复原问题答案。

DEF定义 · Divide–Conquer–Combine

• Divide：确定子问题的范围、数量与规模；
• Conquer：递归求解每个子问题，最小规模直接处理；
• Combine：把子答案合成为当前问题答案。

有些算法的 Combine 很轻，例如快速选择只决定进入哪一侧；有些算法的 Combine 是主体，例如归并排序和逆序对计数。分析复杂度时必须分别计费。

标准模板不是最终答案

Result solve(Problem problem) {
    if (smallEnough(problem)) return directAnswer(problem);
    auto parts = divide(problem);
    std::vector<Result> answers;
    for (const auto& part : parts) answers.push_back(solve(part));
    return combine(problem, answers);
}

模板只能提醒阶段，不能替你回答：子问题是否重叠、拆分是否均衡、合并是否会丢信息、基本情况是否与合同一致。

完整示例：二维战俘矩阵

12E05 · 赦免战俘把边长为 2^n 的方阵分为四个象限：当前层左上象限整体变为 0，其余三个象限继续执行相同规则。

阶段	当前层职责
Divide	用 half=size/2 划分四个坐标区域
Conquer	递归处理右上、左下、右下
Combine	没有数值返回；三个子区域共同构成当前区域
Base	size==1 时没有更小区域

递推式为 $T(s)=3T(s/2)+\mathrm{\Theta }(s^2)$，因为当前层要清零面积为 $s^2/4$ 的左上象限。最终输出本身有 $s^2$ 个元素，因此 $\mathrm{\Theta }(s^2)$ 已是不可避免的下界。

IDEA直觉 · 坐标也是递归合同

二维分治除了规模，还必须传递区域左上角。solve(row,col,size) 比只传 size 更完整：同样大小的子问题位于不同位置，坐标决定写入哪里。

规模减半但只求一个子问题

12E04 · Pow(x,n)有一个半规模子问题；12E07 · 求第 k 小的数在划分后也只进入包含目标下标的一侧。

这类算法仍有分治思想，但递推式形如：

$$T(n)=T(n/2)+f(n),$$

而不是固定的两路递归。若 f(n)=O(1)，总时间为 $O(\log n)$；若 f(n)=O(n)，几何级数求和得到期望 $O(n)$。

WARN易错点 · 分成两半却递归两次同一半

快速幂的 half 必须保存后复用。把 pow(x,n/2) 在乘法两边各调用一次，会把单路递归变成两路递归，复杂度从对数上升到线性。

均衡拆分为什么重要

归并排序总把数组分成近似相等两半，递归深度稳定为 $O(\log n)$。快速选择的划分位置由枢轴决定；若枢轴总是极值，子问题可能从 n 只缩到 n-1，最坏复杂度变成 $O(n^2)$。

三路划分把等于枢轴的元素集中起来，使大量重复值可以一次结束。随机枢轴或更强的选枢轴策略则用于降低持续极端不均衡的概率。

ANTI反例 · “规模变小”不代表足够快

每次从 n 变成 n-1 的递归确实会终止，但深度和总工作量可能都是线性或平方。终止性只证明程序最终结束，不等于复杂度可接受。

结构分治：对象不一定是数组

12E09 · Construct Quad Tree先判断区域是否统一：

• 若统一，整个区域压成一个叶结点；
• 否则分成四个象限，递归构造四个孩子；
• 返回内部结点作为组合结果。

分治在这里同时完成计算与数据结构构造。子问题的输出不是一个数字，而是一棵树。课程使用固定前序 token I/L0/L1，并规定左上、右上、左下、右下顺序，使结构答案可以稳定测试。

先改造问题，再分治

12E16 · Count of Range Sum原本询问连续子数组。先引入前缀和，区间和变为两个前缀和之差；再按前缀下标分治，就能在合并阶段统计左、右两半之间的合法差值。

这说明 Divide 不一定直接作用于题面对象。高质量建模常包含一步表示转换：

连续区间和
  -> 两个前缀和的差
  -> 左前缀下标 < 右前缀下标的数对
  -> 有序两半上的范围计数

用一张表设计分治

问题	需要写出的答案
当前实例	参数描述哪个范围或结构？
基本情况	哪个规模可以直接求？
拆分	子问题有几个，规模各是多少？
独立性	会不会重复求同一状态？
合并	子答案中哪些信息足以恢复当前答案？
代价	Divide、Combine 各花多少时间？
深度	最坏拆分下递归有多深？
稳定性	多解题是否需要规定输出顺序？

自检

1. 分治子问题必须大小完全相等吗？
2. 为什么快速选择通常比完整快速排序少做工作？
3. 四叉树区域若已经统一，为什么必须立即停止拆分？

参考答案

1. 不必，但最好能保证规模显著缩小。均衡拆分常带来对数深度；持续极不均衡可能使复杂度退化。
2. 划分后只有目标秩所在一侧可能包含答案，另一侧无需排序；因此期望工作量形成递减几何级数。
3. 叶结点已经是该区域的最简正确表示。继续拆分既增加结点和时间，也违反“统一区域压成叶子”的输出合同。

延伸阅读

• OI Wiki：分治给出分治框架、常见算法与复杂度入口。
• Hello 算法：分治从适用条件与典型案例解释同一框架。
• 下一节合并答案专门拆解几类 Combine 不变量。