分治算法
基础算法 · 第08节 · 参考《算法竞赛》分治思想
分治
递归树
主定理
减治
基础必掌握
本节目录
分治算法概述
分治视角看归并排序
分治视角看快速排序
二分查找：分治的"减治"变体
归并的应用：逆序对（分治计数）
经典问题：棋盘覆盖
进阶：CDQ 分治（独立课件）
分治 vs 动态规划 / 总结
配套练习
📌 本课的定位
归并排序、快速排序、逆序对这三种算法的完整代码与交互动画已在 09 高级排序 中详细讲解。本节不再重复实现，而是用分治的视角重新审视它们：为什么它们属于分治？复杂度如何用主定理推导？同时补充棋盘覆盖等只有分治才能优雅解决的问题。
1. 分治算法概述
分治算法（Divide and Conquer）是一种重要的算法设计思想，其核心是将一个复杂问题分解成多个规模较小的、相似的子问题，递归地解决这些子问题，再将子问题的解合并得到原问题的解。
T(n) = a × T(n/b) + f(n)
其中：
a：子问题的个数（递归分支数）
b：子问题规模缩小的倍数
f(n)：分解与合并步骤的代价
分治算法的三个步骤
分解（Divide）：将原问题分解成若干个规模较小的、相互独立的子问题
解决（Conquer）：递归地求解各子问题；若子问题规模足够小，则直接求解（递归边界）
合并（Combine）：将子问题的解合并成原问题的解
📌 适用条件
当问题满足以下条件时，适合使用分治：
问题可以分解为若干个规模较小的相同问题
子问题的解可以合并为原问题的解
各子问题之间相互独立，不包含公共子问题（否则应考虑动态规划）
主定理（Master Theorem）
对递归式 T(n) = a·T(n/b) + f(n)，令 c = log_b(a)（子问题的"指数"），则有三种典型情况：
情形条件（f(n) 与 n^c 的关系）结论
①f(n) = O(n^(c-ε))（合并代价小于子问题）T(n) = Θ(n^c)
②f(n) = Θ(n^c · log^k n)（规模相当）T(n) = Θ(n^c · log^(k+1) n)
③f(n) = Ω(n^(c+ε))（合并代价主导）T(n) = Θ(f(n))
✅ 直觉理解
递归树共有 log_b n 层，叶子总数为 a^(log_b n) = n^(log_b a) = n^c。总复杂度由"叶子总代价"与"各层合并代价之和"中较大者决定——这正是上面三种情形的本质。
2. 分治视角看归并排序
归并排序是分治的"标准教材"：分解是对半切，解决是递归排好左右两半，合并则是把两个有序序列用双指针拼成一个有序序列。关键点在于——"合并"这一步让分治完整成立，没有它，子问题的解就无法上升为原问题的解。
主定理推导
这里 a = 2, b = 2, f(n) = O(n)，于是 c = log_2 2 = 1，属于情形 ②（f(n) = Θ(n^1)），得 T(n) = Θ(n log n)。
✍️ 框架（完整实现见 07）
归并的核心递归结构只有三行，体现分治"分解—解决—合并"：
void merge_sort(int l, int r) {
if (l >= r) return; // 递归边界（子问题足够小）
int mid = (l + r) >> 1;
merge_sort(l, mid); // 分解 + 解决（左）
merge_sort(mid + 1, r); // 分解 + 解决（右）
merge(l, mid, r); // 合并（双指针拼有序序列）
}
完整的 merge 实现、源码级讲解与归并排序交互动画请见 07 排序算法 §5。
3. 分治视角看快速排序
快速排序同样是对半分治，但有一个关键区别：它用 partition（分区）把数组按 pivot 分成"≤ pivot"和"> pivot"两部分，分区后每个元素的最终位置已经确定，因此递归处理完左右子区间后不需要再显式合并——合并被"隐含"在了分区步骤里。
复杂度分析
平均情况：T(n) = 2·T(n/2) + O(n) = O(n log n)
最坏情况（已有序，每次 pivot 取极值）：T(n) = T(n-1) + O(n) = O(n²)
平均情形与归并同属主定理情形 ②；最坏情形退化为"只有一侧子问题"，可用三数取中 / 随机化基准规避。
⚡ 优化策略
三数取中法：从首、中、尾取中位数作 pivot，几乎消除最坏情况
随机化基准：随机选一个元素作 pivot
小数组优化：区间较小时改用插入排序（常数更小）
完整的 quick_sort 实现、分区动画与三数取中代码见 07 排序算法 §7–§8。
4. 二分查找：分治的"减治"变体
二分查找每次把搜索区间砍掉一半，但它与前面两种排序略有不同：它只递归处理一个子问题（另一半被直接丢弃），这种"分解后只保留一个分支"的变体称为 减治（Decrease and Conquer）。其递归式是 T(n) = T(n/2) + O(1)，而非分治常见的 a=2。
递归版本（与 07/04 的迭代版互为补充）
// 递归版二分：更直观地体现"减治"结构
int binary_search(int a[], int l, int r, int x) {
if (l > r) return -1; // 区间为空，未找到
int mid = l + (r - l) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) return binary_search(a, mid + 1, r, x); // 只递归右半
else return binary_search(a, l, mid - 1, x); // 只递归左半
}
T(n) = T(n/2) + O(1) = O(log n)
📌 关于二分查找
本节只从"减治"角度给出递归框架。迭代写法、lower_bound / upper_bound 的实现细节、边界陷阱与二分答案，均在 04 二分查找 完整讲解，请移步该课。
5. 归并的应用：逆序对（分治计数）
逆序对统计是把"归并排序"的分治框架拿来计数的经典例子。问题：序列中满足 i < j 且 a[i] > a[j] 的 (i, j) 有多少对？
分治计数思路
分解：把序列对半分成左右两半
递归：分别求出左、右两半内部的逆序对数量
合并计数：在归并过程中，每当从右半取元素 a[j] 而左半还有剩余元素 a[i]，说明 a[i..mid] 全部与 a[j] 构成逆序对，贡献 mid - i + 1 个
✅ 复杂度
沿用归并的 O(n log n) 框架，合并阶段只需在原有比较里加一行 cnt += mid - i + 1。完整代码、带计数的 merge 实现与模板题见 07 排序算法 §6。
6. 经典问题：棋盘覆盖
棋盘覆盖是"只有分治才能优雅解决"的代表问题，在排序之外展示了分治的真正威力。
问题描述
有一个 2k × 2k 的棋盘，其中一个方格被特殊标记（残缺）。用 L 形骨牌（由三个方格组成）覆盖剩余的所有方格，骨牌不能重叠、不能越界。
分治思路
将棋盘分成四个 2k-1 × 2k-1 的子棋盘
特殊方格所在的子棋盘递归求解
另外三个子棋盘的交汇中心放一个 L 形骨牌，使它们各"获得"一个被骨牌覆盖的方格（视作新的特殊方格）
对四个子棋盘递归，直到 size = 1
💡 为什么是分治？
关键技巧是"在三个普通子棋盘的交汇处放一块骨牌"，人为制造出三个新的特殊方格，从而把"一个特殊方格"的问题转化为"四个各含一个特殊方格的更小问题"——这正是分治"把原问题转化为相同结构子问题"的精髓。
代码实现
const int N = 100;
int board[N][N];
int tile = 0;
// (tr,tc): 当前棋盘左上角; (dr,dc): 特殊方格坐标; size: 边长
void chess_board(int tr, int tc, int dr, int dc, int size) {
if (size == 1) return;
int t = tile++;
int s = size / 2;
// 特殊方格在左上象限
if (dr < tr + s && dc < tc + s)
chess_board(tr, tc, dr, dc, s);
else {
board[tr + s - 1][tc + s - 1] = t; // 用骨牌覆盖交汇格
chess_board(tr, tc, tr + s - 1, tc + s - 1, s);
}
// 特殊方格在右上象限
if (dr < tr + s && dc >= tc + s)
chess_board(tr, tc + s, dr, dc, s);
else {
board[tr + s - 1][tc + s] = t;
chess_board(tr, tc + s, tr + s - 1, tc + s, s);
}
// 特殊方格在左下象限
if (dr >= tr + s && dc < tc + s)
chess_board(tr + s, tc, dr, dc, s);
else {
board[tr + s][tc + s - 1] = t;
chess_board(tr + s, tc, tr + s, tc + s - 1, s);
}
// 特殊方格在右下象限
if (dr >= tr + s && dc >= tc + s)
chess_board(tr + s, tc + s, dr, dc, s);
else {
board[tr + s][tc + s] = t;
chess_board(tr + s, tc + s, tr + s, tc + s, s);
}
}
7. 进阶：CDQ 分治（见独立课件）
CDQ 分治（陈丹琦分治）用于处理“修改影响查询”“偏序关系”类问题（三维偏序、带修查询等），是分治的重要拓展。其完整讲解（框架、三维偏序、带修 CDQ、代码模板）已独立成页：《复杂分治（CDQ 分治）》。本节不再展开。
8. 分治 vs 动态规划 / 总结
维度分治动态规划
子问题关系相互独立，无重叠大量重叠，需记忆化
典型递归式T(n)=aT(n/b)+f(n)DP 转移方程（含重叠子问题）
合并方式显式合并 / 隐含（分区）由子问题最优解组合
例子归并、快排、棋盘覆盖背包、最长上升子序列、区间 DP
💡 分治算法的优势
降低复杂度：把 O(n²) 的问题优化到 O(n log n)（排序、逆序对）
结构清晰：递归表达直观，易于正确实现与证明
可并行：子问题相互独立，天然适合并行 / 分布式
降维打击：CDQ 分治把高维偏序降到可管理的复杂度
9. 配套练习
🎯 P1228 【模板】棋盘覆盖
洛谷链接 →
普及+/提高
分治经典题，直接套用本课本节的分治框架
🎯 P3810 【模板】三维偏序（陌上花开）
洛谷链接 →
提高+/省选
CDQ 分治入门题，按 a 排序 + 分治按 b 归并 + 树状数组统计 c
🎯 P1908 逆序对
洛谷链接 →
普及+
分治计数范例，完整代码与动画见 07 排序算法 §6
🎯 P5536 【XR-3】核心城市
洛谷链接 →
普及+/提高
树的直径 + 分治/贪心思想，巩固分治"中心化"直觉
🎯 P1429 平面最近点对
洛谷链接 →
普及+/提高
分治经典几何题：按 x 排序分治，合并时用带状区域剪枝