第6章 · 大事化小、小事化了——分治

来源、目录与技术核对边界

“第6章 · 大事化小、小事化了——分治”以天瓏书店详细书目与目录核对段忠杰、顾业鸣著、中国水利水电出版社、ISBN 9787522615059、245 页以及全书 6 章；该页标出版日期 2023 年 6 月 1 日。河南省政府采购书目记录同一 ISBN、题名、作者和出版社，但出版时间写作 2023 年 5 月。日期口径相差一个月，本课程保留差异，不自行断言哪一天是正式首发日。

对“第6章 · 大事化小、小事化了——分治”而言，公开来源只提供书目和详细目录，不含可授权改写的完整正文；本站的解释、推导、代码、交互、练习和答案均为独立教学重写。目录页第 4 章和第 6 章标题存在明显 OCR 或排版异常，站内按上下文规范化标题，但在清单中披露校正。

“第6章 · 大事化小、小事化了——分治”的技术事实另以Strassen 1969 年快速矩阵乘法原始论文复核：技术来源 1。来源用于检查概念、语言语义或历史算法边界，不把现代竞赛规则静默投射成 2023 年原书的逐字内容。

围绕“怎样证明分解后的子问题、合并步骤、递归终止与复杂度递推都成立？”，先预测正确轨迹，再只注入“只计算递归子问题却遗漏跨分区贡献，使局部正确无法合成整体正确”。若不能用最小反例定位第一处错误决策，就拒绝当前算法解释。

从“递归调用两次就是分治吗”开始

先预测：Fibonacci递归把$n$拆成$n-1$和$n-2$，为什么不被视为高效分治？因为两个子问题高度重叠，递归树反复计算同一状态。分治的收益来自子问题规模缩小且大体独立，再用受控成本合并。

必须明确四件事：何时停止、怎样切分、子答案表示什么、怎样合并而不漏掉跨边界解。

6.1 分治基本介绍

6.1.1 原理

分治基本介绍的原理可写为递推：

$a$是子问题数，$n/b$是子问题规模，$f(n)$是切分与合并成本。让总成本可见。

若$a=b=2$且每层合并总成本$\Theta(n)$，树高$\log_2n$：

Base case必须把规模真正降到可直接求解；若切分产生与原问题同样大的子问题，递归不会终止。

6.1.2 分治和动态规划的区别

分治和动态规划的区别不在“递归还是循环”，而在状态依赖：

• 分治子问题通常由不相交输入区间产生，各算一次后combine；
• 动态规划的不同路径频繁到达同一状态，需要memo或表格合并；
• 二者都依赖最优子结构或可组合摘要，也可组合使用。

归并排序是分治；Fibonacci记忆化是DP；矩阵链DP又会在每个区间状态枚举分割点。算法名称不应替代依赖图分析。

6.2 数乘型分治

数乘型分治利用数字表示的结构减少重复乘法或大整数子乘法。

6.2.1 疯狂的细胞分裂

疯狂的细胞分裂可把“每代乘增长因子$r$，共$t$代”写为$r^t$。逐代乘需要$t-1$次；按指数奇偶递归：

long long power(long long base, unsigned long long exponent) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent & 1ULL) result *= base;
        exponent >>= 1ULL;
        if (exponent) base *= base;
    }
    return result;
}

整数会快速溢出；竞赛题常要求模幂，应把每次乘法用足够宽的中间类型后取模。矩阵快速幂把标量乘法替换为矩阵乘法，可计算线性递推。

6.2.2 简单的乘法

简单的乘法把大整数按base$B$拆成$x=aB+b,y=cB+d$。直接展开需要四个半长乘法：

利用：

BigInt karatsuba(BigInt x, BigInt y) {
    if (small(x) || small(y)) return x * y;
    auto [a, b] = split(x);
    auto [c, d] = split(y);
    BigInt z2 = karatsuba(a, c);
    BigInt z0 = karatsuba(b, d);
    BigInt z1 = karatsuba(a + b, c + d) - z2 - z0;
    return shift2(z2) + shift1(z1) + z0;
}

递推$T(n)=3T(n/2)+O(n)$，得到$O(n^{\log_23})\approx O(n^{1.585})$。小整数上额外分配与加减成本更大，应设置阈值回退普通乘法。

6.3 矩阵乘法的分治

6.3.1 神秘数字

矩阵乘法的分治先观察神秘数字“8”：把两个$n\times n$矩阵各切成四块，结果每块是两个块乘积之和，总共需要8个$n/2$规模矩阵乘法。

递推为：

仅仅分块没有改变指数，但改善cache locality，并为减少递归乘法数提供代数入口。

6.3.2 Strassen快速矩阵乘法

Strassen快速矩阵乘法通过特定加减组合，只做7个半规模乘法，再重建四个结果块：

的渐近优势不代表任意规模更快：padding、临时矩阵、cache、并行库和浮点误差都会提高交叉点。生产实现通常在大块上Strassen、小块回退高度优化的经典kernel。

6.4 线性结构问题的分治

线性结构问题的分治把数组按中点切开。完整答案有三类：全在左半、全在右半、跨越中点。Combine必须构造第三类，否则只取两个子答案会漏解。

6.4.1 自助餐厅（一）

自助餐厅（一）可先建立线性区间模型：每个位置有收益或等待代价，目标找总和最大的连续选择。左、右子问题给出各自最优区间；跨中点答案由左半最佳suffix加右半最佳prefix组成。

long long max_subarray(std::span<const long long> a) {
    if (a.size() == 1) return a[0];
    const std::size_t mid = a.size() / 2;
    long long left = max_subarray(a.first(mid));
    long long right = max_subarray(a.subspan(mid));
    long long suffix = best_suffix(a.first(mid));
    long long prefix = best_prefix(a.subspan(mid));
    return std::max({left, right, suffix + prefix});
}

每层combine线性扫描，总成本$O(n\log n)$。它不是该问题最快算法，线性扫描DP可达$O(n)$；价值在于学习“跨边界摘要”怎样使combine完备。

6.4.2 自助餐厅（二）

自助餐厅（二）进一步把摘要作为接口设计。一个区间若保存总和、最佳prefix、最佳suffix、最佳subarray，两个相邻区间可在$O(1)$合并：

这个monoid式摘要还能用于segment tree：静态分治变成支持区间查询和点更新的数据结构。

6.5 树形结构问题的分治

树天然由根和若干子树组成。树形结构问题的分治先postorder汇总子树，再preorder把根外信息传给孩子。

6.5.1 沟通成本

沟通成本设某节点为中心，目标为它到所有节点距离和。对一个固定root，DFS可同时求depth与subtree size，根答案为：

若对每个节点都重新DFS，成本$O(n^2)$。相邻根之间的大部分距离变化具有统一规律，可以复用。

6.5.2 换根策略

换根策略把根从父节点$u$移动到孩子$v$。$v$子树内的$size[v]$个节点距离都减1，其余$n-size[v]$个节点距离都加1：

void reroot(int u, int parent) {
    for (int v : graph[u]) {
        if (v == parent) continue;
        answer[v] = answer[u] + node_count - 2 * subtree_size[v];
        reroot(v, u);
    }
}

一次postorder求size和初始答案，一次preorder传播所有答案，总成本$O(n)$。这是树上的divide/combine与信息复用结合。

6.6 再看路径规划——地图上的分治

再看路径规划——地图上的分治把大地图切成regions，在每个区域内部预计算边界portal之间的距离，查询时只在起点区域、终点区域和高层边界图上搜索。

正确combine要求任何跨区路径都经过已列出的边界接口；局部摘要必须保存足够的portal-to-portal成本。分区过小会使边界图巨大，分区过大又让局部搜索昂贵，层次化分割需要在预处理、内存与查询时间之间平衡。

正式节点与算法证据

• 分治基本介绍 ：第 1 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 分治和动态规划的区别 ：第 2 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 数乘型分治 ：第 3 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 疯狂的细胞分裂 ：第 4 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 简单的乘法 ：第 5 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 矩阵乘法的分治 ：第 6 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 神秘数字 ：第 7 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• Strassen快速矩阵乘法 ：第 8 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 线性结构问题的分治 ：第 9 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 自助餐厅（一） ：第 10 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 自助餐厅（二） ：第 11 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 树形结构问题的分治 ：第 12 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 沟通成本 ：第 13 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 换根策略 ：第 14 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。
• 再看路径规划——地图上的分治 ：第 15 个正式节点要能回到“子问题覆盖原问题且边界不重不漏，合并恢复完整合同，基例保证终止。”，并给出成功输入与失败反例。

小结

本章从分治基本介绍与原理出发，区分分治和动态规划；在数乘型分治中用疯狂的细胞分裂理解快速幂，用简单的乘法理解Karatsuba。矩阵乘法的神秘数字8引出Strassen快速矩阵乘法的7个递归乘积。

线性结构问题的分治通过自助餐厅（一）与（二）建立跨中点摘要；树形结构问题用沟通成本与换根策略把平方重复降为线性；地图上的分治则把局部路径与边界portal组合。参考文献应继续追踪算法的适用前提、数值稳定性和工程crossover，而不是只保留复杂度指数。

练习与答案

名词解释