分治算法

引言：为什么「分而治之」如此自然

面对一个规模为 $n$ 的问题，如果它具备某种可分解的内部结构，我们往往不必正面强攻。把问题切成若干个规模更小的同构子问题，递归求解后再把答案拼回来——这就是分治（Divide and Conquer）。这并非某种具体算法，而是一套算法设计范式，与贪心、动态规划、回溯并列。

分治的影子无处不在：归并排序把数组对半切，快速排序按 pivot 分两半，最近点对按中线把平面切成左右两半，大整数乘法把数位拆成高低位，Strassen 把矩阵切成子块，快速幂把指数折半，并行计算框架（MapReduce）把数据分片后归约。可以说，凡是能写出 $T(n) = aT(n/b) + f(n)$ 这种递推的地方，都有分治的呼吸。

本文会从分治的三步骨架讲起，给出主定理这一分析利器，再以归并排序、快速排序、逆序对计数三个经典示例为锚点，逐步扩展到最近点对、Karatsuba 大整数乘法、Strassen 矩阵乘法、快速幂、线性时间选择，最后讨论分治与动态规划的本质区别、工程化优化技巧以及常见陷阱。所有示例代码用 C++ 给出，目标是让你读完之后能独立判断「这个问题适不适合分治」「分治的复杂度该是多少」「合并步骤会不会成为瓶颈」。

核心思想：分治三步与正确性直觉

Divide / Conquer / Combine

一个分治算法严格由三步构成：

1. 分解（Divide）：把原问题划分成若干个规模更小的子问题。划分方式决定了递归树形状，也决定了复杂度的 $b$。
2. 解决（Conquer）：递归地求解子问题。当子问题小到某个阈值（递归基）时直接求解，避免无限递归。
3. 合并（Combine）：把子问题的解粘合成原问题的解。这一步的代价 $f(n)$ 往往是复杂度分析的关键，也是许多分治算法「出彩」或「翻车」的地方。

形式化地，分治算法的运行时间满足递推：

$$T(n) = a \cdot T(n/b) + f(n), \quad T(n_0) = \Theta(1)$$

其中 $a \geq 1$ 是子问题个数，$b > 1$ 是规模缩减比，$f(n)$ 是分解与合并的总代价。

正确性直觉：结构归纳

分治的正确性几乎总是建立在结构归纳上。要证明 Solve(P) 正确，只需：

• 递归基：当 $|P| \leq n_0$ 时，Solve(P) 直接返回正确答案。
• 归纳步：假设对所有规模 $< n$ 的子问题 Solve 都正确，证明合并步骤 Combine(Solve(P1), ..., Solve(Pa)) 能还原出 P 的正确解。

这里的关键是子问题的解只依赖子问题自身的输入，而不依赖其它子问题的内部状态。这一点把分治与动态规划划开了界线（后文详述）。归并排序之所以正确，是因为「两个有序段合并后整体有序」这条引理不依赖两段如何变得有序；快速排序正确，是因为「pivot 左边都比它小、右边都比它大」这一划分性质独立于两侧如何继续排序。

什么样的结构适合分治

判断一个问题是否适合分治，可以套三条判据：

1. 可分解：原问题输入能自然切成若干个互不重叠的部分，且每部分仍是同构问题。
2. 可合并：子问题的解存在一个不昂贵的合并方式能拼出原问题的解。如果合并代价 $f(n) = \Theta(n^2)$，而朴素算法也是 $O(n^2)$，那分治就白做了。
3. 子问题独立：子问题之间没有共享状态、没有顺序依赖。这是分治与 DP 的分水岭。

满足这三条的问题，分治几乎是首选。下面我们用主定理把「合并代价如何决定总复杂度」这件事彻底说清楚。

主定理（Master Theorem）：分治复杂度的速算尺

定理表述

设 $T(n) = aT(n/b) + f(n)$，其中 $a \geq 1$，$b > 1$ 为常数，$f(n)$ 渐近非负。令 $n^{\log_b a}$ 为「临界函数」。则：

• 情形一：若 $f(n) = O(n^{\log_b a - \epsilon})$（$f$ 多项式地小于临界函数），则 $T(n) = \Theta(n^{\log_b a})$。叶子代价主导。
• 情形二：若 $f(n) = \Theta(n^{\log_b a})$，则 $T(n) = \Theta(n^{\log_b a} \log n)$。叶子与内部代价势均力敌。
• 情形三：若 $f(n) = \Omega(n^{\log_b a + \epsilon})$（$f$ 多项式地大于临界函数）且满足正则条件 $a f(n/b) \leq c f(n)$（$c < 1$），则 $T(n) = \Theta(f(n))$。根节点代价主导。

速查表

把常见分治算法套进主定理：

算法	$a$	$b$	$f(n)$	临界 $n^{\log_b a}$	情形	$T(n)$
二分查找	1	2	$\Theta(1)$	$n^0=1$	二	$\Theta(\log n)$
归并排序	2	2	$\Theta(n)$	$n$	二	$\Theta(n\log n)$
快速排序（平均）	2	2	$\Theta(n)$	$n$	二	$\Theta(n\log n)$
Karatsuba 乘法	3	2	$\Theta(n)$	$n^{\log_2 3}\approx n^{1.585}$	一	$\Theta(n^{1.585})$
Strassen 矩阵乘法	7	2	$\Theta(n^2)$	$n^{\log_2 7}\approx n^{2.807}$	一	$\Theta(n^{2.807})$
普通矩阵乘法（朴素分治）	8	2	$\Theta(n^2)$	$n^3$	三	$\Theta(n^3)$
最近点对（带预处理）	2	2	$\Theta(n)$	$n$	二	$\Theta(n\log n)$

这张表揭示了一个深刻事实：朴素分治不一定优于朴素算法。矩阵乘法的朴素分治把 $n^3$ 拆成 8 个 $n/2$ 子问题，套主定理三得 $\Theta(n^3)$，跟三重循环一模一样。Strassen 的天才之处在于用 7 次乘法替代 8 次，把 $a$ 从 8 降到 7，临界指数从 3 降到 $\log_2 7 \approx 2.807$，这才换来真正的渐近改进。

主定理的直觉：递归树上谁说了算

把递归树画出来：根节点代价 $f(n)$，下一层 $a$ 个节点各付 $f(n/b)$，再下一层 $a^2$ 个节点各付 $f(n/b^2)$，共 $\log_b n$ 层。每层总代价为 $a^k f(n/b^k)$。

• 若 $f$ 增长慢于临界函数，叶子层（共 $a^{\log_b n} = n^{\log_b a}$ 个）代价堆积成主导，得情形一。
• 若 $f$ 与临界函数同阶，每层代价都接近 $n^{\log_b a}$，共 $\log n$ 层，得情形二。
• 若 $f$ 增长远快于临界函数，根附近几层代价压倒一切，得情形三。

主定理之外：Akra–Bazzi

主定理处理不了 $T(n) = T(n/3) + T(2n/3) + O(n)$ 这种「不等分」递推（快速排序最坏退化时也类似）。此时要用 Akra–Bazzi 定理：找 $p$ 满足 $\sum_i a_i b_i^p = 1$，则

$$T(x) = \Theta\left(x^p \left(1 + \int_1^x \frac{g(u)}{u^{p+1}} du\right)\right)$$

对上面的例子，$1/3^p + (2/3)^p = 1$ 解得 $p=1$，于是 $T(n) = \Theta(n(1 + \int_1^n \frac{u}{u^2}du)) = \Theta(n\log n)$。这印证了「不等分只要合并是线性的，总复杂度仍是 $\Theta(n\log n)$」。

算法框架模板

下面是一个最小可复用的分治骨架，几乎所有分治算法都能往里套：

#include <vector>

// 分治通用骨架：模板参数化为具体的 Solve/Combine
template <typename Problem, typename Answer>
Answer divideAndConquer(Problem p) {
    // 1. 递归基：足够小直接求解
    if (baseCase(p)) {
        return solveDirectly(p);
    }
    // 2. 分解
    auto subs = split(p);
    // 3. 解决：递归子问题
    std::vector<Answer> subAnswers;
    for (auto& s : subs) {
        subAnswers.push_back(divideAndConquer<Problem, Answer>(s));
    }
    // 4. 合并
    return combine(subAnswers, p);
}

实际写代码时不必套这个模板，但它把分治的四要素（基、分、解、合）显式化了。下面我们从最经典的归并排序开始。

示例一：归并排序——分治的教科书

问题描述

给定长度为 $n$ 的数组，使其升序排列。要求时间 $\Theta(n\log n)$，且稳定（相等元素的相对顺序不变）。

思路

• Divide：取中点 mid = (left+right)/2，把数组分成 [left, mid] 与 [mid+1, right] 两段。
• Conquer：递归对两段排序。
• Combine：用双指针把两个有序段合并为一个有序段，代价 $\Theta(n)$。

递推 $T(n) = 2T(n/2) + \Theta(n)$，主定理情形二，$T(n) = \Theta(n\log n)$。稳定性来自合并时「左边不大于右边才取左边」的 <= 判断。

完整可编译代码

#include <vector>

void merge(std::vector<int>& nums, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    
    for (int p = 0; p < k; p++) {
        nums[left + p] = temp[p];
    }
}

void mergeSort(std::vector<int>& nums, int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

复杂度分析

• 时间：无论最好最坏平均都是 $\Theta(n\log n)$——这是归并排序相对快排的最大优势。
• 空间：$\Theta(n)$ 辅助数组。归并排序不是原地排序。
• 稳定性：稳定。

变种与优化

1. 自底向上归并：去掉递归，从长度 1 的段开始两两合并，省去递归栈开销，工程实现更友好。
2. 原地归并：用「手摇算法」（block swap）实现 $O(1)$ 额外空间归并，但常数极大，实战中很少用。
3. Timsort：Python/Java 默认排序。它在小段切插入排序，在已有序段上跳过合并，结合了归并的稳定性与插入排序的小数据优势。

示例二：快速排序——分治的不对称之美

问题描述

对长度 $n$ 的数组原地排序，期望 $\Theta(n\log n)$。

思路

快排与归并的「分治方向」相反：归并的代价在合并，分解几乎免费；快排的代价在分解（partition），合并几乎免费。

• Divide：选一个 pivot，把数组重排成「pivot 左边 $\leq$ pivot，右边 $>$ pivot」。
• Conquer：递归排左右两段。
• Combine：什么都不做——左右两段排好后整体自然有序。

完整可编译代码

#include <vector>
#include <algorithm>

int partition(std::vector<int>& nums, int low, int high) {
    int pivot = nums[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (nums[j] <= pivot) {
            i++;
            std::swap(nums[i], nums[j]);
        }
    }
    std::swap(nums[i + 1], nums[high]);
    return i + 1;
}

void quickSort(std::vector<int>& nums, int low, int high) {
    if (low < high) {
        int pi = partition(nums, low, high);
        quickSort(nums, low, pi - 1);
        quickSort(nums, pi + 1, high);
    }
}

复杂度分析

• 最好/平均：每次 partition 接近对半分，$T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$。
• 最坏：每次 pivot 都是最值，退化为 $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$。在已排序数组上取末元素为 pivot 的实现会触发此最坏情况。
• 空间：$\Theta(\log n)$ 递归栈（平均），最坏 $\Theta(n)$。
• 稳定性：不稳定。partition 的 swap 会打破相等元素的相对顺序。

变种与优化

1. 随机化 pivot：swap(nums[low + rand()%(high-low+1)], nums[high]) 后再 partition。期望复杂度 $\Theta(n\log n)$，对任何输入都稳定。
2. 三数取中（median-of-three）：取 low/mid/high 三处的中位数作 pivot，减少最坏情况概率。
3. 三路划分（Dijkstra 三色）：把数组分成 < pivot / == pivot / > pivot 三段，对大量重复元素场景（如荷兰国旗问题）能把复杂度压到 $\Theta(n)$ 级别。
4. 内省排序（Introsort）：libstdc++ 的 std::sort 实现。快排递归深度超过 $2\log n$ 时切到堆排序，小数组切插入排序。这样既有快排的平均速度，又有堆排的最坏保证。

// 三路划分快排：处理大量重复元素
void quickSort3Way(std::vector<int>& nums, int low, int high) {
    if (low >= high) return;
    int pivot = nums[low];
    int lt = low, gt = high, i = low + 1;
    while (i <= gt) {
        if (nums[i] < pivot)      std::swap(nums[lt++], nums[i++]);
        else if (nums[i] > pivot) std::swap(nums[i], nums[gt--]);
        else                      ++i;
    }
    quickSort3Way(nums, low, lt - 1);
    quickSort3Way(nums, gt + 1, high);
}

示例三：逆序对计数——归并的副产品

问题描述

数组 nums 中，若 $i < j$ 但 nums[i] > nums[j]，称 $(i,j)$ 为一个逆序对。求逆序对总数。朴素 $O(n^2)$ 双重循环在 $n = 10^5$ 时不可接受。

思路

关键观察：在归并排序的合并阶段，当右段元素 nums[j] 被选中放入 temp 时，左段从 i 到 mid 的所有元素都比 nums[j] 大（因为左段已升序）。这些元素原本位置都在 j 之前，于是构成 mid - i + 1 个逆序对。这样把逆序对计数「免费」搭在归并排序上，复杂度从 $O(n^2)$ 降到 $O(n\log n)$。

完整可编译代码

#include <vector>

long long mergeCount(std::vector<int>& nums, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    long long invCount = 0;
    
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            invCount += (mid - i + 1);  // 左边剩余元素都大于nums[j]
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    
    for (int p = 0; p < k; p++) {
        nums[left + p] = temp[p];
    }
    return invCount;
}

long long countInversions(std::vector<int>& nums, int left, int right) {
    if (left >= right) return 0;
    
    int mid = left + (right - left) / 2;
    long long count = 0;
    count += countInversions(nums, left, mid);
    count += countInversions(nums, mid + 1, right);
    count += mergeCount(nums, left, mid, right);
    return count;
}

复杂度分析

• 时间：$\Theta(n\log n)$，与归并排序同阶。
• 空间：$\Theta(n)$。
• 注意返回类型用 long long：$n = 10^5$ 时最大逆序对数 $\binom{n}{2} \approx 5 \times 10^9$，超出 int 范围。

变种

1. 用树状数组/线段树：把值离散化后按位置扫描，每次查询「比当前值大的已插入元素数」。同样是 $O(n\log n)$，但能在线维护，支持动态修改。
2. 三维偏序（CDQ 分治）：逆序对本质是二维偏序 $(i<j, a_i>a_j)$。推广到三维 $(i<j, a_i>a_j, b_i>b_j)$ 用 CDQ 分治仍是 $O(n\log^2 n)$，是计算几何与高级数据结构的核心技巧之一。

示例四：最近点对——分治几何的典范

问题描述

平面上 $n$ 个点，求欧氏距离最近的点对距离。朴素 $O(n^2)$。

思路

• Divide：按 $x$ 坐标排序，取中位数 $x_m$ 把点集切成左右两半 $L$ 和 $R$。
• Conquer：递归求 $L$ 内最近距离 $\delta_L$、$R$ 内最近距离 $\delta_R$，令 $\delta = \min(\delta_L, \delta_R)$。
• Combine：剩下的唯一隐患是「一个点在 $L$、一个点在 $R$」的跨界对。只需考察落在中线两侧宽 $\delta$ 的「条带」内的点。关键引理：把条带内的点按 $y$ 排序后，每个点只需与接下来的至多 7 个点比较。因此合并代价 $O(n)$。

为什么是 7？把条带按 $\delta \times \delta$ 网格切分，左右两半各至多 4 个点能共存而不违反 $\delta$（详细几何论证见 CLRS 33.4 节），所以一个点的 $y$ 邻域内最多 $4+4-1=7$ 个候选。

完整可编译代码

#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

struct Point {
    double x, y;
};

double dist(const Point& a, const Point& b) {
    return std::hypot(a.x - b.x, a.y - b.y);
}

// 合并：处理跨中线点对，band 内按 y 排序后逐点比较 7 个邻居
double closestPairStrip(std::vector<Point>& pts, int left, int mid, int right, double delta) {
    double xm = pts[mid].x;
    // 收集落在 [xm-delta, xm+delta] 条带内的点
    std::vector<Point> band;
    for (int i = left; i <= right; ++i) {
        if (std::fabs(pts[i].x - xm) < delta) band.push_back(pts[i]);
    }
    // 按 y 升序
    std::sort(band.begin(), band.end(),
              [](const Point& a, const Point& b) { return a.y < b.y; });

    double best = delta;
    int n = band.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n && (band[j].y - band[i].y) < best; ++j) {
            best = std::min(best, dist(band[i], band[j]));
        }
    }
    return best;
}

// 前置条件：pts 已按 x 排序
double closestPairRec(std::vector<Point>& pts, int left, int right) {
    if (right - left <= 3) {
        // 递归基：朴素枚举
        double best = std::numeric_limits<double>::max();
        for (int i = left; i <= right; ++i)
            for (int j = i + 1; j <= right; ++j)
                best = std::min(best, dist(pts[i], pts[j]));
        // 保持子段按 y 有序便于合并优化（此处略，朴素实现亦 O(n log n) 总体）
        return best;
    }
    int mid = left + (right - left) / 2;
    double dl = closestPairRec(pts, left, mid);
    double dr = closestPairRec(pts, mid + 1, right);
    double delta = std::min(dl, dr);
    return closestPairStrip(pts, left, mid, right, delta);
}

double closestPair(std::vector<Point> pts) {
    std::sort(pts.begin(), pts.end(),
              [](const Point& a, const Point& b) { return a.x < b.x; });
    return closestPairRec(pts, 0, (int)pts.size() - 1);
}

复杂度分析

• 时间：$T(n) = 2T(n/2) + O(n\log n)$（条带内 std::sort）。套主定理三，$f(n)=n\log n$ 多项式大于临界 $n$，得 $T(n) = O(n\log^2 n)$。
• 优化到 $O(n\log n)$：在递归返回时顺便把子段按 $y$ 归并排序，条带内就不用再 sort，直接归并，$T(n) = 2T(n/2) + O(n)$，主定理二得 $\Theta(n\log n)$。

变种

1. 三维最近点对：分治仍可行，合并步常数变大，渐近仍 $O(n\log^2 n)$。
2. 动态最近点对：用分块或 Delaunay 三角剖分维护，复杂度更高。

示例五：Karatsuba 大整数乘法——把 4 次乘法压到 3 次

问题描述

两个 $n$ 位大整数 $X$ 和 $Y$ 相乘。朴素竖式乘法 $O(n^2)$。

思路

把 $X$ 拆成高位 $X_1$ 和低位 $X_0$：$X = X_1 \cdot B^{n/2} + X_0$，$Y$ 同理。其中 $B$ 是进制（如 $2^{64}$）。则

$$XY = X_1 Y_1 B^n + (X_1 Y_0 + X_0 Y_1) B^{n/2} + X_0 Y_0$$

朴素分治需要 4 次子乘法：$X_1Y_1, X_1Y_0, X_0Y_1, X_0Y_0$，套主定理三仍是 $O(n^2)$，毫无改进。

Karatsuba 的天才一步：观察 $X_1 Y_0 + X_0 Y_1 = (X_1 + X_0)(Y_1 + Y_0) - X_1 Y_1 - X_0 Y_0$，于是只需 3 次乘法：$X_1Y_1$、$X_0Y_0$、$(X_1+X_0)(Y_1+Y_0)$。加减法是 $O(n)$。

递推 $T(n) = 3T(n/2) + O(n)$，主定理一，$T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})$。

完整可编译代码

#include <string>
#include <algorithm>

// 去除前导零
std::string stripZero(std::string s) {
    int i = 0;
    while (i < (int)s.size() - 1 && s[i] == '0') ++i;
    return s.substr(i);
}

// 大数加法
std::string add(std::string a, std::string b) {
    std::string res;
    int carry = 0, i = a.size() - 1, j = b.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        res.push_back(char('0' + sum % 10));
        carry = sum / 10;
    }
    std::reverse(res.begin(), res.end());
    return res;
}

// 大数减法，假定 a >= b
std::string sub(std::string a, std::string b) {
    std::string res;
    int borrow = 0, i = a.size() - 1, j = b.size() - 1;
    while (i >= 0) {
        int d = (a[i--] - '0') - borrow - (j >= 0 ? b[j--] - '0' : 0);
        if (d < 0) { d += 10; borrow = 1; } else borrow = 0;
        res.push_back(char('0' + d));
    }
    std::reverse(res.begin(), res.end());
    return stripZero(res);
}

std::string shift(std::string s, int n) {
    return s + std::string(n, '0');
}

std::string karatsuba(const std::string& x, const std::string& y) {
    int n = std::max(x.size(), y.size());
    if (n == 1) {
        int p = (x[0] - '0') * (y[0] - '0');
        return std::to_string(p);
    }
    n = (n + 1) / 2;  // 高低段长度
    // 把 x,y 左侧补零到等长，便于切分
    std::string xs = std::string(std::max(x.size(), y.size()) - x.size(), '0') + x;
    std::string ys = std::string(std::max(x.size(), y.size()) - y.size(), '0') + y;
    std::string x1 = xs.substr(0, xs.size() - n);
    std::string x0 = xs.substr(xs.size() - n);
    std::string y1 = ys.substr(0, ys.size() - n);
    std::string y0 = ys.substr(ys.size() - n);

    std::string z0 = karatsuba(x0, y0);
    std::string z2 = karatsuba(x1, y1);
    std::string z1 = sub(sub(karatsuba(add(x1, x0), add(y1, y0)), z2), z0);

    // z2 * 10^(2n) + z1 * 10^n + z0
    return add(add(shift(z2, 2 * n), shift(z1, n)), z0);
}

复杂度分析

• 时间：$O(n^{\log_2 3}) \approx O(n^{1.585})$。
• 空间：递归栈 $\Theta(\log n)$。
• 工程上 Karatsuba 的常数较大，通常在 $n$ 大于某个阈值（如几十位）时才切换，小数字用朴素乘法。

推广：Toom–Cook 与 FFT

• Toom–Cook：把数拆成 $k$ 段而非 2 段，用 $2k-1$ 次乘法（插值法），$T(n) = O(n^{\log_k (2k-1)})$，$k=3$ 即 Toom-3 给 $\approx O(n^{1.465})$。
• FFT 乘法：把整数乘法转化为多项式乘法，用快速傅里叶变换在 $O(n\log n)$ 完成。是当前大整数乘法（如 GMP 对极大数）的事实标准。

示例六：Strassen 矩阵乘法——分块矩阵的乘法优化

问题描述

两个 $n \times n$ 矩阵 $A, B$ 相乘，朴素三重循环 $O(n^3)$。

思路

把 $A, B$ 各切成四个 $\frac{n}{2} \times \frac{n}{2}$ 子块：

$$A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}, \quad B = \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix}$$

朴素分块乘法需要 8 次 $\frac{n}{2}$ 阶矩阵乘法：

$$C_{11} = A_{11}B_{11} + A_{12}B_{21}, \quad \ldots$$

仍是 $O(n^3)$。Strassen 构造了 7 个中间矩阵 $M_1, \ldots, M_7$，每个是一次子块乘法，再用加减法组合出 $C_{ij}$。递推 $T(n) = 7T(n/2) + O(n^2)$，主定理一，$T(n) = O(n^{\log_2 7}) \approx O(n^{2.807})$。

七个中间矩阵定义如下（记 $S_1 = B_{12} - B_{22}$ 等，省略具体推导）：

$$\begin{aligned} M_1 &= (A_{11} + A_{22})(B_{11} + B_{22}) \\ M_2 &= (A_{21} + A_{22}) B_{11} \\ M_3 &= A_{11} (B_{12} - B_{22}) \\ M_4 &= A_{22} (B_{21} - B_{11}) \\ M_5 &= (A_{11} + A_{12}) B_{22} \\ M_6 &= (A_{21} - A_{11})(B_{11} + B_{12}) \\ M_7 &= (A_{12} - A_{22})(B_{21} + B_{22}) \end{aligned}$$

$$\begin{aligned} C_{11} &= M_1 + M_4 - M_5 + M_7 \\ C_{12} &= M_3 + M_5 \\ C_{21} &= M_2 + M_4 \\ C_{22} &= M_1 - M_2 + M_3 + M_6 \end{aligned}$$

复杂度分析

• 时间：$O(n^{\log_2 7})$。$n=1024$ 时约 $4.7\times$ 加速（理论），实际因常数大、cache 不友好，加速要在 $n$ 较大时才显现。
• 空间：递归栈 + 中间矩阵 $O(n^2)$。

推广：理论极限

Strassen 之后算法被不断改进：Coppersmith–Winograd $O(n^{2.376})$，到 2023 年的最佳上界约 $O(n^{2.37188})$。但这些算法常数极大，工程上几乎无人用，只在理论复杂度研究中重要。GMP、BLAS 等库对中等规模矩阵仍用 Strassen 或其变种。

示例七：快速幂——分治的最小范例

问题描述

计算 $a^n \pmod m$，朴素 $O(n)$ 在 $n = 10^{18}$ 时不可行。

思路

分治指数：$a^n = (a^{n/2})^2 \cdot (n\text{ 奇则补一个 } a)$。$T(n) = T(n/2) + O(1) = \Theta(\log n)$。

完整可编译代码

// 递归版
long long qpow(long long a, long long n, long long m) {
    if (n == 0) return 1 % m;
    long long half = qpow(a, n / 2, m);
    half = half * half % m;
    if (n & 1) half = half * a % m;
    return half;
}

// 迭代版：按位处理指数，工程上更常用
long long qpowIter(long long a, long long n, long long m) {
    long long res = 1 % m;
    a %= m;
    while (n > 0) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

复杂度分析

• 时间：$\Theta(\log n)$ 次乘法 + 取模。
• 空间：递归版 $\Theta(\log n)$ 栈，迭代版 $O(1)$。
• 陷阱：half * half 在 m 接近 $2^{31}$ 时会溢出 long long 上限。要确保 m < 2^{62}，或改用 __int128。

变种：矩阵快速幂

把「标量乘法」换成「矩阵乘法」，就能在 $O(k^3 \log n)$ 时间内计算 $n$ 阶矩阵的幂。这是求解线性递推（如斐波那契 $F_n = F_{n-1} + F_{n-2}$）的标配：

#include <vector>
using Matrix = std::vector<std::vector<long long>>;

Matrix matMul(const Matrix& A, const Matrix& B, long long m) {
    int n = A.size();
    Matrix C(n, std::vector<long long>(n, 0));
    for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k) if (A[i][k])
            for (int j = 0; j < n; ++j) if (B[k][j])
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m;
    return C;
}

Matrix matPow(Matrix A, long long e, long long m) {
    int n = A.size();
    Matrix R(n, std::vector<long long>(n, 0));
    for (int i = 0; i < n; ++i) R[i][i] = 1;  // 单位阵
    while (e > 0) {
        if (e & 1) R = matMul(R, A, m);
        A = matMul(A, A, m);
        e >>= 1;
    }
    return R;
}

// 斐波那契第 n 项 mod m，O(log n)
long long fib(long long n, long long m) {
    if (n == 0) return 0;
    Matrix T = {{1, 1}, {1, 0}};
    Matrix R = matPow(T, n - 1, m);
    return R[0][0];  // F_n = (T^(n-1))[0][0]
}

示例八：第 k 小与线性时间选择——分治的「不平均」版本

问题描述

无序数组中找第 $k$ 小元素（order statistic）。朴素排序 $O(n\log n)$。能否 $O(n)$？

思路一：Quickselect（期望线性）

借鉴快排的 partition：选 pivot 把数组分成两段。若 pivot 落在第 $k$ 位，直接返回；若 $k$ 在左段，只递归左段；若在右段，只递归右段。

关键区别于快排：只递归一侧，所以递推 $T(n) = T(n/2) + O(n) = O(n)$（期望）。最坏仍 $O(n^2)$。

#include <vector>
#include <algorithm>
#include <cstdlib>

int quickSelect(std::vector<int>& nums, int low, int high, int k) {
    if (low == high) return nums[low];
    // 随机 pivot，避免最坏情况
    int randIdx = low + std::rand() % (high - low + 1);
    std::swap(nums[randIdx], nums[high]);
    int pivot = nums[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (nums[j] <= pivot) std::swap(nums[++i], nums[j]);
    }
    std::swap(nums[i + 1], nums[high]);
    int p = i + 1;
    if (p == k)      return nums[p];
    else if (p > k)  return quickSelect(nums, low, p - 1, k);
    else             return quickSelect(nums, p + 1, high, k);
}

int kthSmallest(std::vector<int> nums, int k) {
    return quickSelect(nums, 0, (int)nums.size() - 1, k);
}

思路二：BFPRT（最坏线性）

Blum、Floyd、Pratt、Rivest、Tarjan 五人在 1973 年给出最坏 $O(n)$ 的选择算法，俗称「中位数的中位数」。

1. 把数组每 5 个一组，共 $\lceil n/5 \rceil$ 组。
2. 各组内排序（常数时间），取各组中位数。
3. 递归调用 BFPRT 求这些中位数的中位数 $M$。
4. 以 $M$ 为 pivot 做 partition。
5. 递归一侧。

为什么最坏线性？关键是 $M$ 保证了至少约 $3n/10$ 个元素 $\leq M$、至少 $3n/10$ 个元素 $\geq M$，所以无论递归哪侧，子问题规模至多 $7n/10$。递推 $T(n) \leq T(n/5) + T(7n/10) + O(n)$，由 Akra–Bazzi 解得 $T(n) = O(n)$。

int bfprtPivot(std::vector<int>& nums, int low, int high);

int bfprtSelect(std::vector<int>& nums, int low, int high, int k) {
    if (low == high) return nums[low];
    int pivotIdx = bfprtPivot(nums, low, high);
    std::swap(nums[pivotIdx], nums[high]);
    int pivot = nums[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (nums[j] <= pivot) std::swap(nums[++i], nums[j]);
    }
    std::swap(nums[i + 1], nums[high]);
    int p = i + 1;
    if (p == k)      return nums[p];
    else if (p > k)  return bfprtSelect(nums, low, p - 1, k);
    else             return bfprtSelect(nums, p + 1, high, k);
}

// 求中位数的中位数，返回其在 [low,high] 中的下标
int bfprtPivot(std::vector<int>& nums, int low, int high) {
    if (high - low < 5) {
        std::sort(nums.begin() + low, nums.begin() + high + 1);
        return (low + high) / 2;
    }
    // 每 5 个一组取中位数，搬到数组前部
    int idx = low;
    for (int i = low; i <= high; i += 5) {
        int j = std::min(i + 4, high);
        std::sort(nums.begin() + i, nums.begin() + j + 1);
        std::swap(nums[idx++], nums[(i + j) / 2]);
    }
    // 递归求这些中位数的中位数
    int mid = (low + idx - 1) / 2;
    bfprtSelect(nums, low, idx - 1, mid);
    return mid;
}

复杂度对比

算法	最好	平均	最坏	备注
排序后取第 k	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	简单粗暴
Quickselect	$O(n)$	$O(n)$	$O(n^2)$	实战最常用
BFPRT	$O(n)$	$O(n)$	$O(n)$	常数大，理论意义更强

工程上 std::nth_element 多用 introselect（先快选，递归深度超阈值切 BFPRT），兼顾平均速度与最坏保证。

分治优化技巧：小数组切插入排序

归并排序、快速排序在 $n$ 很小时，递归调用的常数开销会压过算法本身的渐近优势。当 $n \leq 16$（经验阈值），插入排序的 $O(n^2)$ 反而比 $O(n\log n)$ 的归并/快排更快——因为常数小、cache 友好。

#include <vector>
#include <algorithm>

const int INSERTION_THRESHOLD = 16;

void insertionSort(std::vector<int>& nums, int left, int right) {
    for (int i = left + 1; i <= right; ++i) {
        int key = nums[i];
        int j = i - 1;
        while (j >= left && nums[j] > key) {
            nums[j + 1] = nums[j];
            --j;
        }
        nums[j + 1] = key;
    }
}

void mergeSortOpt(std::vector<int>& nums, int left, int right, std::vector<int>& temp) {
    if (right - left + 1 <= INSERTION_THRESHOLD) {
        insertionSort(nums, left, right);
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSortOpt(nums, left, mid, temp);
    mergeSortOpt(nums, mid + 1, right, temp);
    // 合并：复用单一 temp 缓冲区，避免每次 new
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) temp[k++] = nums[i++];
        else temp[k++] = nums[j++];
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    for (int p = left; p <= right; ++p) nums[p] = temp[p];
}

void mergeSortOpt(std::vector<int>& nums) {
    if (nums.size() <= 1) return;
    std::vector<int> temp(nums.size());
    mergeSortOpt(nums, 0, (int)nums.size() - 1, temp);
}

这套优化的递推变为：

$$T(n) = \begin{cases} \Theta(1) & n \leq n_0 \\ 2T(n/2) + \Theta(n) & n > n_0 \end{cases}$$

渐近仍是 $\Theta(n\log n)$，但常数因子显著降低。其它常见优化：

1. 辅助缓冲区复用：把 temp 提到外层一次分配，递归传入，避免每次 merge 重新 new。上面代码已示范。
2. 检测已有序段：合并前若 nums[mid] <= nums[mid+1]，直接返回，跳过合并。对近乎有序的输入接近 $O(n)$。
3. 原地 swap 而非复制：交替使用 nums 和 temp 作为源/目标，省去最后一次拷贝。
4. 并行化：左右两段递归相互独立，可用线程池并行。这是分治天然适合并行的体现，也是 Fork–Join 框架（如 Java ForkJoinPool）的核心思想。

分治 vs 动态规划：子问题独立性

分治和动态规划（DP）都是「把大问题拆成小问题」，初学者常混淆。区别在子问题是否独立、是否重叠。

子问题独立性

• 分治：子问题互不依赖。归并排序排左半段时不需要右半段的任何信息，逆序对计数中左段贡献的逆序对数与右段无关。因此子问题可以并行求解、可以无记忆化递归。
• DP：子问题共享状态。最长公共子序列 LCS(i,j) 依赖 LCS(i-1,j) 和 LCS(i,j-1)，而这些又依赖更小的子问题。子问题高度重叠，必须用记忆化或表格避免重复求解。

子问题重叠

• 分治：子问题通常不重叠。归并排序把数组切成不交的两段，每个元素只属于一个子问题。
• DP：子问题高度重叠。朴素递归求斐波那契 $F_n$ 的时间是 $O(2^n)$，因为 $F_{n-2}$ 被 $F_n$ 和 $F_{n-1}$ 各算一次。记忆化后变 $O(n)$。

判别口诀

如果同一个小问题在递归过程中会被多次求解，用 DP；如果每个子问题只被求解一次且彼此独立，用分治。

反例：分治也能解「看似 DP」的问题

CDQ 分治用分治思想解决带偏序的统计问题（如三维偏序计数），本质是「分治中嵌套数据结构」，把看似只能 DP/数据结构的问题转化为分治。这提示我们：分治与 DP 的边界并非铁板一块，关键看问题的结构能否被分解。

横向对比：分治家族速览

算法	分解方式	合并代价	总复杂度	关键技巧
归并排序	对半切	$O(n)$	$O(n\log n)$	双指针合并
快速排序	按 pivot 切	$O(1)$	期望 $O(n\log n)$	partition
逆序对计数	对半切	$O(n)$	$O(n\log n)$	合并时统计
最近点对	按中线切	$O(n)$	$O(n\log n)$	条带 + 7 邻居
Karatsuba	高低位切	$O(n)$	$O(n^{1.585})$	3 次乘法替代 4 次
Strassen	分块切	$O(n^2)$	$O(n^{2.807})$	7 次乘法替代 8 次
快速幂	指数折半	$O(1)$	$O(\log n)$	平方折半
Quickselect	按 pivot 切	$O(1)$	期望 $O(n)$	只递归一侧
BFPRT	按 5 元组切	$O(n)$	最坏 $O(n)$	中位数的中位数
CDQ 三维偏序	按 $x$ 切	$O(n\log n)$	$O(n\log^2 n)$	嵌套归并/树状数组

共性：分解方式决定递归树形状（参数 $b$），合并代价 $f(n)$ 决定主定理情形。「分治算法设计的核心不在分解，而在合并」——这是 Karatsuba 与 Strassen 给我们的最大启示。

实战场景

竞赛中的应用

1. 归并/逆序对：模板题，$n \leq 5\times10^5$。变种包括「计算最少相邻交换使数组有序」（等价于逆序对数）。
2. CDQ 分治：处理三维偏序、四维偏序，是高级数据结构（树套树）的轻量替代。
3. 点分治：树上路径统计（如「树上距离为 $k$ 的点对数」）的经典做法，把树按重心切开递归。
4. 快速幂 / 矩阵快速幂：线性递推、图上计数、组合数取模的标配。
5. 分治 FFT：处理形如 $f_i = \sum_{j<i} g_j f_{i-j}$ 的卷积递推，$O(n\log^2 n)$。

工程中的应用

1. 并行计算：MapReduce、Fork–Join、CUDA reduce 本质都是分治——数据分片、各片独立处理、最后归约合并。
2. 数据库：外部排序（多路归并）、分片查询（partition pruning）。
3. 数值计算：FFT（信号处理、大整数乘法）、分块矩阵运算（BLAS Level 3）、多精度算术（GMP 用 Toom–Cook + FFT）。
4. 图算法：最近公共祖先的 Tarjan 离线算法、平面图最近点对。
5. 编译器：语法分析（递归下降）、 SSA 构造中的支配树计算（Lengauer–Tarjan）。

一个真实的工程例子：外部归并排序

当待排序数据 $100\text{GB}$，内存只有 $1\text{GB}$ 时，内存排序不可行。外部归并排序：

1. Divide：把数据切成 $100$ 个 $1\text{GB}$ 的块，每块读入内存排序后写回磁盘。代价 $O(n\log M)$，$M$ 是内存容量。
2. Conquer：每块已是有序文件。
3. Combine：$k$ 路归并（用最小堆维护 $k$ 个指针），逐元素输出。归并趟数 $\log_k (n/M)$。

总 IO 代价 $O\left(\frac{n}{B} \log_{M/B} \frac{n}{B}\right)$（$B$ 为块大小），这是分治在「数据规模超过内存」时的标准应对。

常见陷阱与边界条件

1. int 中点溢出

int mid = (left + right) / 2;            // 危险：left+right 可能溢出
int mid = left + (right - left) / 2;     // 安全

当 left, right 都接近 INT_MAX 时，第一种写法溢出成负数，导致死循环或越界。std::midpoint（C++20）是最规范的写法。

2. 递归终止条件错误

if (left == right) return;   // 单元素时返回，正确
if (left > right) return;    // 也正确，多一层无意义递归
if (left >= right) return;   // 推荐：合并上述两种

漏写终止条件会无限递归栈溢出；写成 if (left == right) 在空区间（left > right）时仍会进入死循环。归并排序里 mid = (left+right)/2 在 left == right 时 mid == left，递归 mergeSort(left, mid) 不变，无限递归——必须用 left >= right 兜底。

3. 逆序对计数溢出

$n = 10^5$ 时最大逆序对数 $\binom{10^5}{2} \approx 5\times10^9$，超过 int（约 $2.1\times10^9$）。返回类型必须 long long，累加变量也必须 long long。

4. 快速幂中间结果溢出

half * half % m 在 $m > 2^{31}$ 时，half * half 可达 $2^{62}$，逼近 long long 上限 $2^{63}-1$。若 $m$ 接近 $2^{62}$，需用 __int128 或快速乘（二进制拆分乘法）：

long long mulMod(long long a, long long b, long long m) {
    long long res = 0;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (res + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return res;
}

5. 最近点对的「7 个邻居」前提

「条带内每个点只需比较 7 个邻居」依赖子问题内的最小距离 $\delta$。若实现时把 $\delta$ 取成全局已知的更小值，结论仍成立；但若递归返回的 $\delta$ 错误，7 邻居结论失效，会漏解。务必确保 delta = min(dl, dr) 后再进 strip。

6. Karatsuba 的递归基与对齐

Karatsuba 在 $n=1$ 时直接相乘返回。但若输入长度不齐（如 $x$ 是 5 位、$y$ 是 3 位），切分时要先补零对齐。上面代码用 std::string(size_diff, '0') + x 补齐。漏补会导致 substr 越界或结果错误。

7. BFPRT 的实现陷阱

BFPRT 的常数很大，实现细节多：

• 每 5 个一组取中位数后，要把这些中位数搬到数组前部，再递归求中位数的中位数。直接对中位数开新数组空间开销大。
• 求出 pivot 后，partition 必须返回 pivot 的最终下标，而非像快排那样只返回分割位置。下标必须与 pivot 值一一对应。
• 工程上几乎都用 std::nth_element 而非自己写 BFPRT。

8. 分治与递归深度

$n = 10^7$ 时，$\log_2 n \approx 23$，递归深度不是问题。但若分解不均（如某些点的 $b \to 1$），深度可能达 $O(n)$，栈溢出。对策：

• 改写成迭代（如自底向上归并）。
• 尾递归优化（快排的「短段先递归，长段尾递归」技巧）。
• 显式栈模拟递归。

// 快排尾递归优化：短段递归，长段循环
void quickSortTailRec(std::vector<int>& nums, int low, int high) {
    while (low < high) {
        int pi = partition(nums, low, high);
        if (pi - low < high - pi) {
            quickSortTailRec(nums, low, pi - 1);
            low = pi + 1;
        } else {
            quickSortTailRec(nums, pi + 1, high);
            high = pi - 1;
        }
    }
}

这样递归深度被限制为 $O(\log n)$。

9. 浮点比较的 epsilon

最近点对中距离比较不能用 ==，要用 std::fabs(a-b) < eps。但求最小值时直接 std::min 即可，无需 epsilon——浮点比较的陷阱主要出现在相等性判断，不在最值更新。

10. 分治解空间与栈空间

分治的额外空间往往来自合并步骤的临时缓冲。归并排序需 $O(n)$；快排原地但栈 $O(\log n)$；最近点对需 $O(n)$ 存条带；Strassen 需 $O(n^2)$ 存中间矩阵。在内存受限场景（嵌入式、ACM 限内存题）要特别留意。

小结

分治是算法设计中最自然的范式之一。它的力量不在某个具体技巧，而在一套统一的设计方法论：找到可分解的结构、保证合并代价可控、用主定理或 Akra–Bazzi 验证渐近复杂度。

回到本文开头的三步骨架：

1. Divide：选好分解方式。等分（归并、最近点对）、按值分（快排、Quickselect）、按位分（快速幂）、按块分（Strassen、Karatsuba）——分解方式直接决定 $b$ 和 $a$。
2. Conquer：写好递归基。小到阈值就切直接解（插入排序、朴素枚举），既减少常数又终止递归。
3. Combine：合并步骤是分治设计的「主战场」。Karatsuba 把 4 次乘法压到 3 次、Strassen 把 8 次压到 7 次、归并的双指针 $O(n)$ 合并、最近点对的 7 邻居引理——所有「神来之笔」都在这里。

判断一个问题适不适合分治，回到三条判据：可分解、可合并、子问题独立。三者满足，分治几乎一定是最优解的候选；若子问题重叠，转向 DP；若需要贪心选择，转向贪心。

最后给一份学习路径建议：

• 入门：归并排序、快速排序、逆序对计数、快速幂。把这四个写到肌肉记忆。
• 进阶：最近点对、Karatsuba、Quickselect/BFPRT。理解主定理的三个情形。
• 高级：Strassen、CDQ 分治、点分治、分治 FFT。开始把分治作为「与数据结构/DP 平起平坐的设计工具」来用。
• 理论：读 CLRS 第 4 章（分治）、第 28 章（矩阵运算）、第 33.4 节（最近点对）；读 Akra–Bazzi 原论文；追矩阵乘法的最新上界。

分治的美妙之处在于：它把「大问题」转化为「同构的小问题」，让递归成为最自然的表达。当你下次面对一个看似无解的庞大问题，先问自己一句——「能不能切成两半？」答案往往比想象中更乐观。