优选算法这个系列写到分治专题，其实是很多人的分水岭。前面几章讲遍历、双指针、动态规划，多少还有套路可循；一进入分治，问题就变成了：为什么这道题要拆成两半？拆完之后又要做哪些额外动作？更扎心的是，递归代码一看就懂，一关掉视频自己写就错。我做过一段时间算法相关的辅导，发现大多数人卡住的点根本不是"递归不会写"，而是没搞清楚分治真正的工作量在哪里。这篇文章我就按自己的理解，把分治从直觉、复杂度、经典题到实战高频坑完整过一遍，适合正在刷算法题、准备面试或竞赛的读者，也适合工作里偶尔需要手写复杂算法的人。
1. 分治的直觉：与其说是拆，不如说是借
1.1 从三个小问题看分治的通用动作
先聊几个特别朴素的问题。
问题A：在一堆扑克牌里找最大的一张。大多数人会一张张看，这没问题。但如果是两个人合作找呢？一个人看前一半，一个人看后一半，各自找到最大值，再比较一下，就能确定整副牌的最大值。这就是分治。
问题B：统计一个数组里有多少对逆序（前面的数比后面大）。直接两层循环当然是O(n^2)，但如果你手头刚好有归并排序的框架，把数组拆成两半，先统计左半内部的逆序对、右半内部的逆序对，再统计一个在左一个在右的逆序对，三部分加起来就是答案。关键是第三部分可以在合并两个有序数组的过程中顺带算出来，复杂度直接降到O(n log n)。
问题C：在一个有序数组里找某个元素。二分查找几乎人人都学过，但你有没有想过，它本质上就是每次把问题拆成"左边一半"和"右边一半"，然后只进入其中一半继续做同样的操作。它之所以快，是因为每一步都丢弃了一半的规模。
这三个问题放在一起，你会发现分治的固定动作其实就三个：分解（把原问题切分成若干子问题）、解决（递归处理，或者直接解决足够小的子问题）、合并（把子问题的结果汇总成原问题的答案）。不同题目的差别，只在于切的方式、子问题的数量、以及合并动作的复杂度。
1.2 "分"很容易，"合"才是灵魂
很多教程讲分治，会把大量篇幅放在"递归"两个字上，仿佛只要会写递归就会分治。我的感受恰恰相反：递归调用这一段几乎不用动脑子，真正决定解法优劣的，永远是"拆完之后你要额外做的合并动作"。
打个比方：分治像公司拆任务。把一个大任务拆给两个小组，这是分；每个小组自己内部搞定，这是治；但你最后肯定要有人把两边的成果汇总、解决边界衔接问题，这就是合。很多问题难就难在，两边各做各的都很顺利，一到交接就出Bug。
比如最大子数组问题，在一个数组里找连续的一段，使段内数字之和最大。如果只知道用前缀和或者暴力枚举，确实也能做。但用分治的思路是：数组从中间劈开，答案只可能是三种情况之一——完全在左半边、完全在右半边、跨越中间线。前两种交给递归，第三种必须由你写一个"从中间向左扫一遍再向右扫一遍"的循环来完成。这个跨越中间的合并逻辑，才是整道题的核心考点。
所以学分治，建议你每看完一道题都问自己：这道题的合并阶段做了什么？为什么合并阶段的复杂度和递归加在一起仍然可控？这两个问题想明白了，分治就算入门了。
1.3 分治、动态规划、贪心到底怎么区分
学算法的人都会纠结：这道题到底用分治还是DP？其实两者有非常清晰的分界线。
- 分治的子问题是互不重叠的：左边归左边，右边归右边，最多在合并时跨过边界扫一遍。它不依赖"把同一个子问题的结果存下来复用"，因为根本不会重复计算同一个子问题。
- 动态规划的子问题则是相互重叠的：f(i) 的计算可能依赖 f(i-1) 甚至 f(i-2)，同一个值会被反复需要，所以你要用表格把它记下来。
- 贪心则更进一步：它根本不在子问题之间做比较，而是每一步选当前看起来最好的，放弃"尝试所有拆分方案"的机会。
所以拿到一道题，先判断子问题之间会不会互相重复。会重复，考虑DP；不会重复，且合并动作有明确意义，考虑分治。这两个判断差不多能筛掉一半的纠结。剩下少数的题，其实殊途同归，比如最大子数组问题，Kadane算法只用一遍扫描就解决了，但它的正确性证明里，依然能看到分治的思考痕迹。
2. 复杂度分析：主定理要会推，不能只会背
2.1 递归树比公式更直观
许多算法书会把主定理（Master Theorem）写成三个Case，然后让学生死记。我的建议是：公式要理解，但最开始一定要用递归树把形状画出来。
以归并排序为例，T(n) = 2T(n/2) + O(n)。这棵树长什么样？根节点是规模为n的合并操作，开销O(n)；下一层有两个节点，每个规模n/2，合并开销O(n/2)，总计O(n)；再往下有四个节点，每个规模n/4，总开销还是O(n)。这样的层一共有log2(n)层，每层开销都是O(n)，所以总复杂度是O(n log n)。
这个"每层开销相同"的情况，对应的就是 f(n) 刚好等于 n^(log_b(a)) 的量级。这里的a是每次拆出的子问题个数，b是规模缩小的倍数。归并排序每次拆2个、规模减半，log_b(a) = log2(2) = 1，而 f(n) = n 也确实是一次的，所以每层总开销恒定。
画出递归树之后，主定理的三个分支其实就是三句话：
- 如果根节点的合并开销比叶子节点数增长慢，总开销由叶子数决定，也就是 n^(log_b(a)) 主导；
- 如果两者同量级，每一层的开销都一样，总开销就是"每层开销乘以层数"；
- 如果根节点的开销主导，那总开销基本上就是合并部分的开销 f(n)。
用这个视角去判断"哪个量级是主导"，比死记三个Case靠谱得多。尤其遇到a不是整数、b不是2的情况，画出两层递归树，很快就能看出趋势。
2.2 一个括号就能拆掉主定理的坑
主定理最大的坑，在于 f(n) 里的 n 到底代表什么。我见过很多人在一道"把数组分成5份，每份规模是原来的1/3，合并开销是O(n^2)"的题目上翻车，原因是他们一看 f(n) = n^2，就兴奋地套用Case 3，却忘了先算 n^(log_b(a)) 是多少。
这里a=5，b=3，log3(5)约等于1.465。n^1.465和n^2相比，后者增长更快，说明合并开销主导，所以答案是O(n^2)。如果你不动笔算，仅凭"5个分支，规模1/3"就猜一个O(n log n)，那就大错特错了。
分治复杂度的计算，本质上就是比较两个东西谁长得快：递归过程产生的叶子节点总数，和每次合并动作的开销。叶子节点数由拆分方式决定，合并开销由题目本身的性质决定。这两个量级之比，直接锁定了最终复杂度。所以做题时养成习惯：每次写完递归式，先在草稿纸上画两层递归树，算出n^(log_b(a))，再比较大小。这个习惯比记任何公式都有用。
2.3 把合并开销算丢：我犯过的典型错误
分享一个我自己实际犯过的错误。有一道题要求把数组分成两半，递归处理，合并阶段需要"把两个部分的所有元素两两比较一遍"。我当时想，合并时如果不做任何优化，对每对元素比较一次，那就是O(n^2)。但我直接写了递归式 T(n) = 2T(n/2) + O(n^2)，算出来总复杂度是O(n^2)。解法当然不是错的，只是没有任何意义，因为排序后整体扫描的复杂度也是O(n^2)甚至更低，分治没有带来任何收益。
这个问题的本质在于：分治的价值，在于让合并动作的总开销低于"直接面对整个数组"的开销。归并排序的合并是O(n)的，虽然每层都要扫一遍，但每层只扫一次，总开销O(n log n)；如果你的合并动作是O(n^2)，那每层开销随着树往上快速膨胀，最终根节点的开销直接把叶子层的收益吞掉。
所以拿到一道分治题，先不要急着写递归，先估算合并开销。如果合并开销看起来无法压到O(n)或者O(n log n)以下，这道题八成不适合用分治做，或者需要换一种合并策略。这个判断，能帮你省下大量瞎写递归的时间。
3. 四个必须手撕的经典场景
分治的经典例子很多，但真正值得反复手撕的，我认为是四个：逆序对计数、最大子数组、最近点对、快速幂。前两个帮你掌握"合并阶段怎么写"；第三个帮你理解"分治为什么能减少比较次数"；第四个则是分治思想在非数组问题上的典型延伸。
3.1 逆序对计数：归并排序的副产品
题目背景是给一个数组，统计有多少对(i, j)满足 i < j 且 arr[i] > arr[j]。直接两层循环是O(n^2)，数据规模到10万就基本卡死，需要优化到O(n log n)或更优。
分治解法其实就三步：
- 把数组从中间劈开，先统计左半内部的逆序对；
- 统计右半内部的逆序对；
- 统计一个在左、一个在右的逆序对。
前两步递归就行。第三步怎么高效做？关键在"两边各自有序"这一点上。如果左右两边都已经排成升序，那么对于右半的某个元素 arr[j]，左半中所有比它大的元素 arr[i]（i在左半范围内）都和它构成逆序对。而左半已经有序，所以可以用二分找到第一个大于arr[j]的位置，左半从那个位置到结尾的所有元素都是答案。
但更常见的做法是直接在归并排序的合并过程中顺便统计：合并两个有序数组时，每当从右半取出一个元素放入结果数组，说明左半当前的剩余元素都大于它，于是答案累加左半剩余元素的数量。
贴一个最直接的Python实现：
def merge_sort_count(arr): if len(arr) <= 1: return arr, 0 mid = len(arr) // 2 left, inv_left = merge_sort_count(arr[:mid]) right, inv_right = merge_sort_count(arr[mid:]) merged = [] inv = inv_left + inv_right i = j = 0 len_left, len_right = len(left), len(right) while i < len_left and j < len_right: if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 inv += len_left - i # 左半从i到末尾都大于right[j] merged.extend(left[i:]) merged.extend(right[j:]) return merged, inv这里的关键就是一行：inv += len_left - i。只有从左半取数时才不增加逆序对计数，因为左半元素本来排在前边；从右半取数时，说明左半从当前位置开始往后的所有元素都会大于当前取出的右半元素，这些全部构成逆序对。
这个题的训练价值在于：让你明白合并阶段不一定要额外遍历"跨区间"的元素，而是可以在已有操作（排序合并）里顺带完成统计。这种思路在竞赛和面试里特别重要，因为它通常能把额外的时间开销压到零。
提示：如果你对"为什么左右各有序很关键"还不清楚，建议手写一个长度为3的数组，把归并过程一步步画出来。画完整个过程，你大概率就不再需要背这段代码了。
3.2 最大子数组：答案必然藏在三种位置之一
给定数组，找一段连续子数组，使和最大。这个问题用Kadane算法一遍扫描就能解，但分治版本是理解"跨区间合并"最好的入门题。
思路是把数组从中点分成两半。最终的最大子数组，只可能是：
- 完全在左半；
- 完全在右半；
- 跨过中点，也就是从中间往左延伸一段、再往右延伸一段。
前两种递归返回，第三种需要单独计算。怎么算？从中间开始向左扫，记录累加过程中的最大值；再从中间加一向右扫，记录累加过程中的最大值。两个最大值相加，就是跨中点的最大子数组和。
核心代码片段：
def max_crossing(arr, left, mid, right): left_sum = float('-inf') cur = 0 for i in range(mid, left - 1, -1): cur += arr[i] left_sum = max(left_sum, cur) right_sum = float('-inf') cur = 0 for j in range(mid + 1, right + 1): cur += arr[j] right_sum = max(right_sum, cur) return left_sum + right_sum然后递归主体就是：分别求左、右、跨中点的最大值，三者取max。
def max_subarray(arr, left, right): if left == right: return arr[left] mid = (left + right) // 2 left_max = max_subarray(arr, left, mid) right_max = max_subarray(arr, mid + 1, right) cross_max = max_crossing(arr, left, mid, right) return max(left_max, right_max, cross_max)复杂度上，每层递归都要做一次O(n)的跨中点扫描，递归层数O(log n)，所以总复杂度O(n log n)。虽然不如Kadane的O(n)，但它的意义在于：你不会只在"线性扫描能解决"的问题上打转，而是能看到分治如何把"任意位置"的问题，变成"三种确定位置"的问题。
我练习这个题时的最大收获，是真正理解了什么叫做"把未知问题转化成已知子问题"。最大子数组的任意位置是不可枚举的，但一旦你把它分类为左、右、跨中点，每一类都有确定的求法，题目就变得可做了。
3.3 最近点对：常数优化绝不是抠细节
平面上给n个点，找距离最近的两个点。暴力做法两两比较，O(n^2)。用分治可以压到O(n log n)，而且这个压制的思路，比代码本身更重要。
基本流程：
- 按x坐标排序，从中间分成左右两半；
- 递归求左半最近点对距离d1，右半最近点对距离d2，取d = min(d1, d2)；
- 关键一步：只考虑x坐标在"中点横坐标±d"范围内的点，也就是可能跨过中点且距离小于d的点对；
- 对这些点按y坐标排序，然后依次检查相邻的点，一旦两个点y坐标差超过d，就停止内层循环，因为后面的点不可能更近。
很多人以为第4步只是常数优化，其实不是。它把最差情况下的比较次数限制在一个很小的常数内。原因是从候选集中任取一点，以它为中心、d为边长的一个区域内，最多只能有常数个点——否则左右半内部必然出现更近的点对，这与d的定义矛盾。
这里贴一个结构清晰的Python版本，重点看分治的骨架和合并阶段的剪枝逻辑：
import math def brute_force(points): n = len(points) best = float('inf') for i in range(n): for j in range(i + 1, n): best = min(best, dist(points[i], points[j])) return best def dist(p, q): return math.hypot(p[0] - q[0], p[1] - q[1]) def closest_pair(points): if len(points) <= 3: return brute_force(points) mid = len(points) // 2 mid_x = points[mid][0] left_res = closest_pair(points[:mid]) right_res = closest_pair(points[mid:]) d = min(left_res, right_res) strip = [p for p in points if abs(p[0] - mid_x) < d] strip.sort(key=lambda p: p[1]) for i in range(len(strip)): for j in range(i + 1, len(strip)): if strip[j][1] - strip[i][1] >= d: break d = min(d, dist(strip[i], strip[j])) return d很多初学者写这道题时，会漏掉"只取±d范围内点"的剪枝，然后发现复杂度依然是O(n^2)，于是断言分治没用。实际只要这个剪枝加上，复杂度就能从O(n^2)降到O(n log n)。
这道题真正的坑，在于排序策略。如果每一步都在递归内部重新按x排序，复杂度会退化成O(n log^2 n)甚至更差。正确的做法是先在外面按x排序一次，递归分割时直接截取区间，这样排序开销不会重复。按y排序这一步，严谨的做法是在合并阶段用归并排序按y合并，能保持全程O(n log n)；如果你只是为了理解，每次递归里临时sort也能跑出正确答案，但要清楚它多了一个log。
3.4 快速幂：分治思想不是只能切数组
如果只把分治理解成"数组从中间切开"，你会错过一个非常实用的场景——快速幂。
计算a^n，最朴素的做法是乘n次，O(n)。但如果你用分治视角看：a^n可以写成：
- 如果n是偶数：a^n = (a^(n/2))^2
- 如果n是奇数：a^n = a * (a^((n-1)/2))^2
每次规模减半，合并动作是常数次乘法，复杂度O(log n)。递归版可以写成：
def fast_pow(a, n): if n == 0: return 1 if n % 2 == 1: return fast_pow(a, n - 1) * a half = fast_pow(a, n // 2) return half * half但结合实际场景，递归版有一个小问题：n很大时，递归调用栈会占用额外空间，而且有人会不小心把fast_pow(a, n // 2)写两遍，造成重复计算。我更推荐迭代版的二进制分解写法：
def fast_pow_iter(a, n): res = 1 base = a while n > 0: if n & 1: res *= base base *= base n >>= 1 return res这两种写法本质是同一个思想，但迭代版省掉了递归栈。如果题目要求结果取模，就在每步乘法后取模，注意中间值溢出问题。
快速幂的启发是：分治的"切分"对象可以是抽象的规模参数，不一定是物理上的数组区间。之后你会看到许多数学计算、矩阵乘积、斐波那契数列加速，都复用同一个"规模减半、合并结果"的模式。所以学分治，一定要跳出"切数组"的思维定式。
4. 分治实战里的高频坑：合并、边界、全局状态
这一节完全来自我在刷题和带人过程中反复见到的错误。分治代码看起来短，但一错就非常隐蔽，因为它不是错在语法上，而是错在思维逻辑上。
4.1 合并阶段漏掉"跨区间"的情况
这是分治题里最常见的坑。典型症状：递归到底层返回的结果是正确的，但整体答案不对，而且往往是偏小。
最大子数组题最容易演示这个问题。如果你只写了
return max(left_max, right_max)而忘了cross_max，你会发现对于 [1, 2, 3, -1, 4, 5] 这种"正数连在一起"的数组，答案就会错。因为最大的子数组可能横跨中点，比如 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 这个经典例子，最大子数组 [4, -1, 2, 1] 恰好跨越中点。
排查这类错误的方法很简单：造一个明确跨越中点的测试用例，比如 [2, -1, 2]，最大子数组是 [2, -1, 2]，和是3，恰好跨越中点。如果递归返回2而不是3，那基本可以确定合并阶段漏写了跨区间逻辑。
所以凡是"答案可能是任意连续区间"的题，都要认真想想：合并时要不要额外枚举一种跨中点的情形？最大子数组、和为特定值的连续子数组计数、某些区间最值类问题，都有这个隐患。
4.2 递归基不是越小越稳
另一个常见认知是"递归基设得越小越安全"，于是有人把归并排序的递归基设为"数组长度为0"。听起来严谨，但会导致一个尴尬的问题：长度是1的数组还要再切分吗？长度是0的数组从哪里切分？这些都需要额外分支处理。
更合理的递归基是len(arr) <= 1。长度为0或1都直接返回，不需要再切分。对于最近点对这类问题，递归基通常设为 n <= 3，因为3个点以内直接暴力比较比递归更快，也避免分割线出现"左空右空"的边界灾难。
递归基的选择原则是：让递归在合法、有意义的最小规模上停止，同时保证这一步不需要依赖"下一层递归"的结果。多花30秒想清楚递归基，能帮你避免大量越界运行错误。
4.3 中位数和下标偏移：两种写法不可混用
分治里最经典的边界陷阱，除了递归基，还有取中点和区间表示方式。我在这上面栽过多次，后来总结出一套固定的写法：
- Python习惯左闭右开 [left, right)，mid = left + (right - left) // 2，递归调用 [left, mid) 和 [mid, right)。
- C++里则常写左闭右闭 [left, right]，mid = left + (right - left) // 2，递归调用 [left, mid] 和 [mid + 1, right]。
两种都能写对，就怕混着用。我见过最经典的错误是：一个人用左闭右闭的区间定义，却把递归调用写成了[left, mid]和[mid, right]，这样mid位置的元素会被重复计算两次，在计数类问题里直接导致结果翻倍。
另一个细节：(left + right) // 2在极端情况下可能溢出（C++里尤其明显，当left和right都接近int上限时），所以更稳妥的是left + (right - left) // 2。这个写法既不溢出，语义也更清晰。
4.4 全局变量和"带返回值的递归"打架
有些初学者习惯用全局变量存答案。比如逆序对计数，他们在递归函数内部不return计数结果，而是直接累加到全局 ans 上。
思路没错，但很容易出两类问题：
- 多次测试用例之间，忘记清空全局 ans，导致结果叠加；
- 递归分支较多时，某个分支提前return，导致全局变量累加漏掉一部分。
我建议一律用返回值递归。每层递归明确返回"这层的子结果"，由上层合并。这样函数纯粹，测试方便，也不容易产生状态残留。如果确实需要在递归里更新一个临时数组（比如归并排序的辅助数组），尽量通过参数传入并在使用后清理，避免临时内容污染下一次调用。
注意：遇到需要在多个测试数据上反复调用的分治函数，第一件事是确认全局状态是否干净。我吃过不少亏，最后发现Bug都出在"上一个用例的残留数据混进了下一个用例"。
5. 从模板到灵活：哪些题该用分治，哪些不该
学完前面的经典题，很容易产生一种"万物皆可分治"的错觉。但实际做题和工作里，分治并不是银弹。这一节聊一聊怎么判断，以及分治思维向日常开发的迁移。
5.1 能用但没必要：当线性扫描足够快时
我一直强调，分治的价值在于把复杂度从O(n^2)或指数级降到O(n log n)甚至更低。但如果某个问题本来就有一个O(n)的线性解法，分治版本通常只是"徒增复杂度"的练习，工程上并不可取。
典型例子就是最大子数组。面试官如果非要你用分治写，你能写出来是加分项；但如果实际业务里遇到类似需求，直接用Kadane线性扫描就好，不仅更快，代码也更短、更不容易出错。
做选型时，我的优先级大致是这样：
- 有没有O(n)的扫描解法？有就不用分治；
- 子问题之间是否重叠？重叠就用DP或记忆化搜索；
- 问题能否通过排序、二分、堆等前置操作解决？能就先想简单方案；
- 只有前面都否定，或者你明确需要在"比较型合并"上做优化（如逆序对、最近点对），才考虑分治。
5.2 分治解不动的问题长什么样
分治也有明显不擅长的场景，常见的有：
- 子问题之间存在强耦合，比如最长公共子序列，子问题天然重叠，更适合DP；
- 答案依赖全局信息，比如求整个数组的众数，如果只是切两半分别统计，合并时很难高效得出正确众数；
- 递归深度本身会成为瓶颈的场景，比如某些链式递归O(n)深度，可能把栈空间撑爆；
- 合并阶段无法压到近线性的问题，分治往往带不来收益。
当你发现题目满足以上特征时，就可以果断放弃分治路线，转去找其他解法。这不是技术不行，而是算法选型的一部分。
5.3 分治思维在工作中的迁移
最后说一个容易被忽略的点：分治思想在工程实践里比在刷题里更常见。你写的排序模块、数据库的分区合并、MapReduce的map-reduce流程、日志系统的分桶归并，底层全是分治。
我在实际工作中写过不少数据处理流程，最常用的模式就是：把一天的数据按小时切分统计，再合并成全天报表；把一个大文件按行数切成多个小块并行解析，最后再汇总。写这些代码时，我用的思考方式跟分治刷题完全一致：先定义清楚"原子任务"的规模，再定义合并规则，最后处理边界和去重。
所以别把分治只当成面试题，它在系统设计和大数据处理里，是一种基本的问题抽象方式。刷题训练收获的，不只是能AC某道题，而是形成一种"如何把一个大规模问题切成可控小问题并正确合并"的本能。
分治这个专题，到这里就告一段落了。回想自己学它的过程，最大的心得其实是：不要沉迷于递归的魔法感，要时刻问自己"分完怎么合"。合得漂亮，才叫分治；合不出来，那只是把一个难题拆成了一堆难题。
再分享一个练习上的小技巧：每做完一道分治题，强制自己用文字写出"分解方式、递归基、合并逻辑、时间复杂度"四行总结。坚持几道以后，你会发现自己对题目结构的敏感度会明显提高。这个习惯我至今还在用，读别人的复杂代码时，也是靠它快速定位核心逻辑。
