13 分治（Divide and Conquer）
GESP 5 级CSP-J / NOIP 核心CSP-S
级别标注：GESP 5 级（考级要求）/ CSP-J、NOIP 核心（竞赛进阶：归并排序、二分答案、棋盘覆盖、平面最近点对）。
一、分治思想
分治 = 分 + 治：把大问题拆成若干规模更小的子问题，分别解决后再合并结果。
三步骤： 1. 分解（Divide）：将问题拆成更小的同类子问题。 2. 解决（Conquer）：递归求解子问题；子问题小到可直接解决。 3. 合并（Combine）：把子问题的解合并成原问题的解。
分治适合"可拆分、子问题独立、可合并"的问题。
形象理解分治像老师把全班分成小组打扫卫生：先把大教室分成几个小区域（分解），每个小组负责一块（解决），最后汇总检查（合并）。前提：每个区域独立可分工，合起来就是整间教室。
考级视角看到题目满足三个特征就用分治：可拆成同类型子问题、子问题互相独立、能合并答案。GESP 5 级笔试常让你判断某解法是否属于分治思想，用这三条对照即可。
二、分治的代表：归并排序
（完整实现见第 6 章）核心思想：把数组对半拆，递归排好两半，再线性合并 —— 时间复杂度 O(n log n)。
C++ 实例
// 分治的核心骨架（以归并排序示意）：拆 → 治 → 合
void mergeSort(int l, int r) {
if (l >= r) return; // 治之最小：单元素天然有序
int mid = (l + r) / 2; // 1) 分解：一分为二
mergeSort(l, mid); // 2) 解决左半
mergeSort(mid + 1, r); // 3) 解决右半
// 4) 合并：线性扫两个有序区间，见第 6 章完整实现
}形象理解归并排序像把两叠按顺序排好的卷子合成一叠：两个手指各指一叠开头，谁小先拿谁，O(n) 就能合并完。先拆到单张（天然有序），再层层合并，整叠就排好了。
易错点归并模板最容易错在合并时漏拷贝：把
tmp 临时数组写回原数组时，下标必须是 l + i 而不是从 0 开始，否则数据错乱。建议先把归并排序默写三遍再上考场。三、分治的更多应用
3.1 快速排序（见 6 章，按 pivot 划分）
3.2 快速幂（分治思想：二分指数）
C++ 实例
// 快速幂：指数折半，把 O(n) 降到 O(log n)
long long fastPow(long long a, long long n, long long mod) {
long long res = 1; // 结果初始为 1
while (n > 0) { // 二进制逐位处理指数
if (n & 1) res = res * a % mod; // 当前位是 1 就乘上 a
a = a * a % mod; // a 自平方（a^(2^k)）
n >>= 1; // 指数右移一位
}
return res;
}
// fastPow(2, 10, 1000000007) 计算 2^10 mod 10000000073.3 二分答案（分治/二分的典型竞赛题型）
对"可行解"（答案）进行二分搜索，把"判定最难"转化为"单调性判定"。
C++ 实例
// 例：切绳子 —— 求能切成 >= k 段时的最大长度（二分答案）
// 判定函数：长度 len 能否切出 >= k 段
#include <iostream>
using namespace std;
const int N = 100005;
int a[N], n, k; // a: 各绳长度, k: 需要段数
bool check(int len) {
long long cnt = 0; // 总段数可能很大，用 long long
for (int i = 0; i < n; i++) cnt += a[i] / len;
return cnt >= k; // 能否凑够 k 段
}
int main() {
int l = 1, r = 1000000000, ans = 0; // 二分区间
n = 5; k = 7;
int data[5] = {100, 90, 50, 40, 30};
for (int i = 0; i < n; i++) a[i] = data[i];
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) { ans = mid; l = mid + 1; } // 可行则尝试更大长度
else r = mid - 1; // 不可行则缩小
}
cout << ans << endl; // 能切 7 段的最大公共长度
return 0;
}3.4 逆序对（归并排序扩展，见 6 章）
合并时若右边元素先被取走，则左边剩余个数即新增逆序对。
3.5 棋盘覆盖（经典递归分治）
4^k - 1 个骨牌覆盖缺一格的 2^k×2^k 棋盘；把棋盘四等分，中间放一个 L 形骨牌让每个小棋盘都"缺一格"，递归。
形象理解快速幂像翻倍法算账：算 2^10 不乘 10 次，而是 2→4→16→256→…，把指数二进制拆分，只做 log n 次乘法。二分答案像猜价格游戏：每次报中间价，根据“高了/低了”砍掉一半范围。
考级视角二分答案是 CSP-J 几乎必考的得分点：看到“最大…的最小值 / 最小…的最大值”这类最值最值题，十有八九是二分答案。模板：
while (l <= r) + check(mid) 单调判定。四、分治的时间复杂度分析（主定理思想）
形如 T(n) = 2T(n/2) + O(n) 得 O(n log n)（归并）；若T(n) = T(n/2) + O(1) 得 O(log n)（二分）。常用递归树估算即可。
形象理解复杂度像叠罗汉的人数：每次劈成两半（n/2），一共能劈 log2(n) 层；每层合并要花 O(n) 力气——总共 O(n log n)。二分每层只花 O(1)，总共 O(log n)。
易错点
mid = (l + r) / 2 在 l、r 都接近 2^31 时会整数溢出变成负数，二分直接死循环。统一写 l + (r - l) / 2 更安全，竞赛模板都这么写。五、易错点 / 常见坑点
- ⚠️ 递归边界必须正确：
l >= r或空区间要及时return，否则栈溢出。 - ⚠️ mid 溢出：
mid = (l + r) / 2在 l+r 超 int 时会溢出，慎用l + (r - l) / 2。 - ⚠️ 归并排序合并时的
tmp拷贝遗漏会丢数据。 - ⚠️ 二分答案的单调性要提前确定（判定函数是否随答案单调），否则二分无效。
- ⚠️ 分治递归中全局数组被多次使用时注意赋值覆盖。
- ⚠️ 快速排序退化问题（见 6 章）。
六、考级要求 vs 竞赛进阶
- 考级要求（GESP 5 级）：分治概念、归并排序、快速排序、二分思想（与递归结合）。
- 竞赛进阶（CSP-J/NOIP）：二分答案（最大化/最小化问题）、归并排序求逆序对、三分、平面最近点对（提高组）、CDQ 分治等进阶方向。二分答案在 CSP-J 是几乎必会的得分点。
七、课内练习建议
- 手写归并排序并复用模板求逆序对。
- 手写快速幂（分治+位运算）。
- 二分答案例题：切绳子、木材最多段、最大最小化（牛牛的房间距离）。
- 尝试棋盘覆盖的手工推演（4×4）。
- 用对拍验证：二分答案的正确性依赖单调性。