第 49 章 分治算法——大而化小

---

🏗️ 前情回顾：第 48 章的贪心"一条路走到黑"，简单但不可靠。本章的主角是分治——另一个用递归实现的经典范式。你早在第 44 章的汉诺塔和 M6 的归并排序中就见过它了。分治的核心是分→治→合：把大问题切成几个同类型的子问题，各自解决再合并。

---

🎯 本章目标

学完这一章，你能：

• 掌握分治三步骤：分、治、合
• 区分分治和减治（每次缩小规模但不合并）
• 深入理解归并排序的分治结构
• 用分治法求最大子段和（O(n log n)）
• 了解平面上最近点对的简化版分治思路
• 理解分治的递归树和复杂度分析（主定理入门）

---

📖 故事引入

老师布置了一份超难的作业：统计全校 3000 名学生的期末成绩，算出平均分、最高分、最低分，还要排出年级前 100 名。

你作为课代表，一个人干 3000 份？太慢了。

聪明的做法：把 3000 份分给 30 个班长，每人统计 100 份。班长把各自的结果交给你，你汇总一下。30 份工作同时进行，效率提高了 30 倍。

更聪明的是，每个班长也可以把自己的 100 份再分给几个小组长……层层往下分，最后每个人只要处理很少的几份。

这就是分治：把一个复杂的大问题，分解成若干个结构相同但规模更小的子问题，各自解决后，把结果合并起来。

你看，汉诺塔是这样（n 个盘子 → 先解决 n-1 个），归并排序也是这样（整个数组 → 先排左半和右半）。本章，我们把分治这把武器耍得更溜。

---

🧱 知识讲解

49.1 分治三步骤

步骤	英文	说明	归并排序的例子
分	Divide	把原问题切成若干子问题	数组从中间切成两半
治	Conquer	递归解决每个子问题	分别排序左右两半
合	Combine	把子问题的解合并成原问题的解	合并两个有序数组

// 分治的通用框架（伪代码）
返回类型 solve(问题) {
    if (问题足够小) return 直接求解;           // 边界
    
    拆分成子问题1, 子问题2, ...;              // 分
    结果1 = solve(子问题1);                   // 治
    结果2 = solve(子问题2);
    ...
    return 合并(结果1, 结果2, ...);           // 合
}

49.2 分治 vs 减治

这两个概念容易混：

	减治（Decrease & Conquer）	分治（Divide & Conquer）
子问题数量	1 个	≥ 2 个
是否合并	不需要合并	需要合并
例子	阶乘 n!=n×(n-1)!、二分查找	归并排序、汉诺塔
复杂度和	T(n) = T(n-1) + O(1)	T(n) = 2T(n/2) + O(n)

简单的判断方式：如果递归调用只有一次（self-call once），是减治；如果多次（self-call multiple times）且需要合并结果，是分治。

49.3 归并排序回顾

归并排序是分治的教科书级案例（你在 M6 已学过，这里加深理解）：

分：把数组 a[l..r] 分成 a[l..mid] 和 a[mid+1..r]
治：递归排序左右两半
合：合并两个有序子数组

void mergeSort(int a[], int l, int r) {
    if (l >= r) return;              // 边界：1个元素天然有序
    int mid = l + (r - l) / 2;
    mergeSort(a, l, mid);            // 治左
    mergeSort(a, mid + 1, r);        // 治右
    // 合：合并两个有序段
    int i = l, j = mid + 1, k = 0;
    int tmp[100005];
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (i = 0; i < k; i++) a[l + i] = tmp[i];
}

递归树可视化（n=8）：

          [0..7]
         /      \
      [0..3]    [4..7]
      /    \    /    \
   [0..1] [2..3] [4..5] [6..7]
   /  \   /  \   /  \   /  \
 [0] [1] [2] [3] [4] [5] [6] [7]

共 log₂ 8 = 3 层，每层合并总代价 O(n)，总复杂度 O(n log n)。

49.4 最大子段和（分治法）

问题：给定数组 a[1..n]，找和最大的连续子数组，返回最大和。

比如 {-2, 1, -3, 4, -1, 2, 1, -5, 4} → 最大子段和 = 6（子数组 {4, -1, 2, 1}）。

分治思路：

把数组分成左半 [l..mid] 和右半 [mid+1..r]

最大子段和可能出现在三种位置：
  ① 完全在左半部分 → 递归求左半的最大子段和
  ② 完全在右半部分 → 递归求右半的最大子段和
  ③ 跨越中点 → 必须包含 mid 和 mid+1，向两侧延伸

取三者最大值

int maxSubarraySum(int a[], int l, int r) {
    if (l == r) return a[l];                  // 边界：只有一个元素
    
    int mid = l + (r - l) / 2;
    
    // ① 左半最大
    int leftMax = maxSubarraySum(a, l, mid);
    // ② 右半最大
    int rightMax = maxSubarraySum(a, mid + 1, r);
    
    // ③ 跨越中点的最大
    // 从 mid 往左延伸的最大后缀和
    int leftSum = 0, maxLeftSum = -1e9;
    for (int i = mid; i >= l; i--) {
        leftSum += a[i];
        maxLeftSum = max(maxLeftSum, leftSum);
    }
    // 从 mid+1 往右延伸的最大前缀和
    int rightSum = 0, maxRightSum = -1e9;
    for (int i = mid + 1; i <= r; i++) {
        rightSum += a[i];
        maxRightSum = max(maxRightSum, rightSum);
    }
    int crossMax = maxLeftSum + maxRightSum;
    
    return max({leftMax, rightMax, crossMax});
}

复杂度：T(n) = 2T(n/2) + O(n) → O(n log n)。（注：这个问题有 O(n) 的线性解法——Kadane 算法，但分治法体现了"切分+合并"的思维。）

49.5 平面上最近点对（简化版）

问题：平面上有 n 个点，找距离最近的一对点，输出它们的距离。

暴力：O(n²)。分治可做到 O(n log n)。

分治思路（简化叙述）：

1. 按 x 坐标排序所有点
2. 分：用一条竖线 x = midX 把点分成左右两半
3. 治：递归求左半最近距离 dL 和右半最近距离 dR
4. 合：令 d = min(dL, dR)。但还要考虑"跨线"的点对——
   只有 x 坐标在 [midX-d, midX+d] 范围内的点才可能产生比 d 更近的点对
   把这些点按 y 坐标排序，检查每个点附近最多 7 个点

💡 这里不要求你完整实现最近点对——它代码较长，主要让你理解分治的"合"这一步有多精巧。"合"是分治中最见功力的部分。

49.6 分治的复杂度分析

分治的复杂度通常用递推式表示，用主定理（Master Theorem）求解：

形如 T(n) = a·T(n/b) + O(n^d)	复杂度
d > log_b a	O(n^d)
d = log_b a	O(n^d · log n)
d < log_b a	O(n^{log_b a})

• 归并排序：T(n)=2T(n/2)+O(n)，a=2,b=2,d=1。d = log₂2 = 1 → O(n log n)
• 最大子段和分治：同上，O(n log n)
• 二分查找（减治）：T(n)=T(n/2)+O(1)，a=1,b=2,d=0。d = log₂1 = 0 → O(log n)

🧠 主定理不要求死记，但知道"切几份、每层合并花多少时间"决定了最终复杂度就够了。

---

✋ 动手试试

试试 1：改写归并排序，让它能同时统计数组的"逆序对"数量（i<j 但 a[i]>a[j]）。提示：在合并步骤中，当右半元素被放入 tmp 时，左半还没放进去的元素都大于它——这就是逆序对。

试试 2：用分治法实现最大子段和，在数组 {2, -4, 5, -2, 3, -1, 8, -3} 上测试。手工验证中间"跨越点"的计算逻辑。

试试 3：对比最大子段和的三种解法——暴力 O(n³)、前缀和优化 O(n²)、分治 O(n log n)、Kadane O(n)，在小规模 (n=1000) 上运行对比时间。

---

⚠️ 容易犯的错

错 1：混淆分治和减治

❌ 把阶乘也算成分治 → 阶乘只有 1 个递归调用，是减治

✅ 分治要求切分成多个子问题（≥2 个）并且需要合并

错 2："合"这步写错了顺序

❌ 归并排序中合并时忘记把左右剩余元素拷贝完

✅ 合并循环结束后，用 while 把左右指针到头的元素全部追加

错 3：分治的递归太深导致栈溢出

❌ 最大子段和分治在 n=10^5 时可能栈溢出（深度 log n 一般还好）

✅ 对于一维问题，分治通常不会太深（log₂ 10^5 ≈ 17 层），放心用

错 4：跨越中点的计算漏了边界

❌ 最大子段和中"跨越中点"只拿了 mid 往左一格、mid+1 往右一格

✅ 必须从 mid 延伸到 l，从 mid+1 延伸到 r，取累加过程中的最大值

---

📝 练习

基础题

1. 选择题

（1）分治算法的三步骤是？
A. 选择→插入→删除   B. 分→治→合   C. 输入→处理→输出   D. 递归→回溯→剪枝

（2）归并排序的分治复杂度是？
A. O(n)   B. O(n log n)   C. O(n²)   D. O(log n)

（3）以下哪个不是分治算法？
A. 归并排序   B. 汉诺塔   C. 二分查找   D. 快速幂

2. 填空题

（1）分治三个步骤：____、____、____。

（2）最大子段和分治中，跨越中点的子段 = 左半____后缀 + 右半____前缀。

（3）T(n) = 2T(n/2) + O(n) 的复杂度是____。

提高题

3. 编程题 — 逆序对计数

用归并排序的分治框架统计数组中的逆序对数量。输入 n 和数组，输出逆序对总数。

4. 编程题 — 快速幂（分治版）

用分治思想实现 a^b mod p：a^b = a^(b/2) × a^(b/2)（b 偶）或 a × a^(b/2) × a^(b/2)（b 奇）。要求 O(log b)。

挑战题

5. 编程题 — 棋盘覆盖

一个 2^k × 2^k 的棋盘，恰好有一个方格是"特殊的"。用 L 形骨牌（占 3 个方格）覆盖所有非特殊方格。输出覆盖方案。

提示：这是经典的分治题——把棋盘 4 等分，特殊格所在的那份递归处理，其他三份在靠近中心的位置各"人造"一个特殊格。

---

🧠 本章小结

分治 = 分 → 治 → 合

三步骤：
  ① 分（Divide）：把原问题切成 ≥2 个同类子问题
  ② 治（Conquer）：递归解决每个子问题
  ③ 合（Combine）：把子问题的解合并

分治 vs 减治：
  分治 = 多个子问题 + 需要合并（归并排序）
  减治 = 1个子问题  + 不合并（阶乘、二分查找）

经典应用：
  归并排序 → T(n)=2T(n/2)+O(n) → O(n log n)
  最大子段和 → 三选一：左半/右半/跨越中点
  最近点对 → 分治+带状区域检查

主定理（直觉）： 
  每次切 k 份，每层合并花 O(n) → O(n log n)
  每次切 1 份，每层合并花 O(1) → O(log n)

---

📝 配套练习

共5题。分治三步骤(分解→解决→合并)每题用一种应用场景展示。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1908	https://hydro.ac/p/luogu-P1908	分治、归并、逆序对
◆ 拓展	luogu-P1115	https://hydro.ac/p/luogu-P1115	分治视角最大子段和
◆ 拓展	luogu-P1010	https://hydro.ac/p/luogu-P1010	递归输出、分治表达
◆ 拓展	luogu-P1257	https://hydro.ac/p/luogu-P1257	分治、平面最近点对
◆ 拓展	luogu-P1498	https://hydro.ac/p/luogu-P1498	分治、分形图

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 4 道◆拓展题，覆盖不同变式和细节。

---

配套练习

共5题。分治三步骤(分解→解决→合并)每题用一种应用场景展示。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1908	https://hydro.ac/p/luogu-P1908	分治、归并、逆序对
◆ 拓展	luogu-P1115	https://hydro.ac/p/luogu-P1115	分治视角最大子段和
◆ 拓展	luogu-P1010	https://hydro.ac/p/luogu-P1010	递归输出、分治表达
◆ 拓展	luogu-P1257	https://hydro.ac/p/luogu-P1257	分治、平面最近点对
◆ 拓展	luogu-P1498	https://hydro.ac/p/luogu-P1498	分治、分形图

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 4 道◆拓展题，覆盖不同变式和细节。

自查清单：

• [ ] 我能说出分治三步骤并在代码中对应
• [ ] 我能区分分治和减治
• [ ] 我理解归并排序的分治结构和 O(n log n) 的由来
• [ ] 我能用分治写出最大子段和的解法
• [ ] 我了解最近点对的分治思想（不要求完整实现）
• [ ] 我能用递归树直观理解分治的复杂度

---

🚀 下章预告：分治把问题一分为二，而倍增恰恰相反——把规模翻倍、翻倍、再翻倍！一张纸对折 30 次有多厚？2^30 层，超过 100 公里！这就是翻倍的力量。第 50 章，我们来见识二进制世界里的"指数爆炸"——快速幂、倍增查找，以及未来 LCA 算法的预告！⚡