分治作为一种算法思想在力扣周赛里很少被单独点名考察。它通常藏在排序类题目的合并阶段、区间统计类题目的递归分解、或者需要把复杂度压到对数级的大数据面题里。周赛 514 这一场如果以分治为观察入口会发现很多题目并不需要复杂技巧真正拉开差距的是能不能在递归拆分和结果合并之间找到正确的信息流。这篇文章从分治出发整理一套适合周赛 514 以及类似场次的思考路径先理解分治的落点再掌握可复用的代码骨架最后用检查清单去定位为什么递归跑不出正确答案。这篇文章适合正在刷力扣热题、准备周赛、或者面试前想复习排序与区间统计类算法的读者。看完后你至少能完成三件事给一道题快速判断它是否值得用分治处理在归并、逆序对、最近点对、快速幂这几类模板之间找到统一结构当递归结果不对时能按顺序排查是出口、划分、合并还是复杂度出了问题。1. 为什么从分治出发看周赛 5141.1 分治不是单一模板而是一整套思维路径分治的通俗含义是把一个大问题拆成若干规模更小、结构相似的子问题先解决子问题再把子问题的结果合并成原问题的答案。它的技术定义一般包含三个步骤划分、递归治理、合并。放到力扣周赛的场景里这个定义仍然成立但真正的难点不是递归本身而是“合并阶段要处理什么信息”。很多选手遇到数组区间题、配对题、统计题时第一反应是枚举或排序却忽略了题目可能在考察分治的合并规律。分治有时候不以“递归”的形式出现而是以“排序后合并”“按中点拆分后统计”“树形结构自底向上计算”的形式出现。从周赛 514 的视角看分治更应该被理解成一套操作路径先看原问题是否能拆成同构子问题再看子问题答案如何合并。如果这两个问题都能回答代码结构通常很稳定如果不能回答说明题目可能不是分治题而是动态规划、贪心或二分答案。1.2 周赛题目里分治最常见的四种落点竞技题中分治不会只出现在一道写着“请用分治”的题里。它通常藏在下面四种题型中。题型形态典型场景分治落点合并阶段要做什么常见复杂度区间统计类求逆序对、满足条件的区间数量、区间最大子段和按中点拆左右区间统计横跨左右区间的贡献O(n log n)排序与顺序类归并排序、链表排序、快速选择第 k 大递归排序左右部分合并两个有序序列O(n log n)几何与配对类最近点对、平面最近点统计按坐标拆左右区域只处理边界带内的点对O(n log n)数值与结构类快速幂、矩阵快速幂、表达式求值按规模折半递归组合小规模结果O(log n)这几个落点对应到周赛里往往不是大段代码而是某个关键函数统计逆序对时在 merge 里加一行计数最大字段和时在跨中点部分求一个左后缀和右前缀快速幂时把 n 变成 n//2 后递归。真正区分选手水平的地方就是能不能在短时间内选出对应合并策略。1.3 分治与其它算法的边界什么时候该用分治不是所有能递归的问题都适合分治。分治的适用条件可以浓缩成三条子问题与原问题同构子问题之间尽量独立能把子问题答案在可控代价内合并。如果子问题之间有大量重叠计算比如斐波那契数列的朴素递归应该优先用动态规划如果题目只需要从一段区间里排除错误答案应该优先用二分如果数据规模很小直接 O(n^2) 枚举反而更稳。这里要特别区分二分的分治。二分不是分治它只保留了“划分”和“排除”没有“合并”分治则必须把左右子问题的结果合到一起。快速排序和归并排序虽然是两个典型分治但它们的合并成本完全不同快排的划分阶段承担了大部分工作归并的合并阶段是核心。周赛里见到“把数组分成两部分分别处理后还要合并结果”的描述时才应该优先考虑分治。2. 把分治拆成三个可执行环节2.1 划分如何选择切分点分治的第一步是划分。数组类问题通常选择中点mid (left right) // 2链表类问题通常用快慢指针找中间节点快速排序类问题则按 pivot 把数组分成小于和大于两个区域。选择切分点时要保证子问题规模和原问题同构否则递归函数无法统一处理。常见的错误是只关注“能不能拆开”不关注“拆得是否均匀”。如果每次都拆成 1 和 n-1 两个子问题递归深度会退化成 O(n)归并排序就变成了 O(n^2)。周赛题目的数据范围如果给到 10^5递归深度 O(n) 很可能直接触发栈溢出或超时。检查划分效果最直接的方法是打印递归深度或观察算法是否在极限数据下稳定运行。2.2 治理递归与子问题的边界“治理”阶段要做两件事设计递归出口以及把当前区间切分后交给递归函数处理。递归出口不是越简单越好。它要返回“当前规模下的基础答案”而不是随便写一个if left right: return就结束。比如求区间最大子段和时单个元素的基础答案是元素本身统计逆序对时单个元素的逆序对数量是 0。递归调用的顺序也有讲究。绝大多数分治模板先递归处理左右子区间再做合并快速排序则是先 partition 划分再递归两侧。如果顺序写反比如在排序前就尝试合并合并阶段拿到的数据状态不是预期的结果必然出错。建议写递归函数时先写出口再写递归调用最后写合并逻辑合并逻辑要单独提取成函数方便用测试用例单独验证。2.3 合并容易被忽略的信息回传合并是分治三个环节里最容易出错的一环。很多题目表面上像分治实际难点全部在合并阶段。以逆序对为例归并排序在合并两个有序数组时如果左半部分当前元素大于右半部分当前元素那么左半部分剩余元素都与该右半部分元素构成逆序对这时需要一次性统计多个逆序对。这个例子的关键点是统计发生在 merge 阶段而且它只统计“横跨左右区间”的逆序对。左右区间内部的逆序对已经在递归过程中计算过不能在合并阶段重复统计。这个问题在周赛中非常典型排序结果正确但答案是 0原因就是合并阶段忘记统计跨区间信息或者统计时把内部信息又多算了一遍。2.4 复杂度分析分治的时间与空间分治递归式一般写成 T(n) a T(n/b) O(n^c)。a 是子问题个数b 是规模缩小的倍数O(n^c) 是划分和合并的代价。根据主定理实际复杂度取决于 c 与 log_b(a) 的大小关系。条件复杂度典型例子c log_b(a)O(n^(log_b(a)))朴素矩阵乘法c log_b(a)O(n^c log n)归并排序c log_b(a)O(n^c)部分暴力优化在周赛里不必严格套主定理但要形成两个直觉如果合并阶段是 O(n) 且每次拆一半整体是 O(n log n)如果合并阶段是 O(n^2) 且拆一半整体复杂度往往不可接受。写代码前先估算合并代价能避免写完才超时的尴尬。3. 周赛 514 中分治题型的上手路径3.1 如果题目要求统计区间贡献尝试整体二分或 CDQ周赛里经常出现一类描述给定数组统计满足某个大小关系的区间数量或者统计所有区间某种权值的总和。暴力枚举左右端点是 O(n^2)数据范围稍大就会超时。此时可以尝试分治把区间按中点拆成完全在左边、完全在右边、横跨中点三类。前两类递归处理第三类在中点附近用双指针或排序统计。这种思路并不需要特别高深的 CDQ 分治概念。它的核心是“跨中点的贡献单独算”。实现时可以先写一个只统计横跨区间贡献的函数再用小样例验证函数本身是否正确最后再套递归。如果横跨区间的贡献能 O(n) 或 O(n log n) 算出整体就是可接受的复杂度。3.2 如果题目包含合并过程先把合并逻辑写对有些题目乍看和分治无关但描述里有明确的“把两个结果合并成新结果”的过程。比如合并两个有序链表、把两个部分的结果相加、把左右子树的值组合成父节点值。这类题目可以先不急着递归先把“合并且返回结果”的纯函数写出来。它的输入是两个已经处理完的子结果输出是合并后的结果。把合并逻辑独立出来有一个好处可以直接构造小数据测试不用通过递归去触发正确性判断。递归的框架一旦写错错误会隐藏在很多层调用里单独测试合并函数能更快定位问题。完成合并函数后再套递归只需验证递归出口和调用方式。3.3 如果题目和排序相关逆序对是切入点排序本身在周赛里更多是前置工具但围绕排序的“顺序关系”往往依赖分治统计。逆序对问题就是一个经典入口。它考察的能力包括能否写出正确的归并排序合并逻辑能否在合并阶段插入统计逻辑是否能避免重复统计内部逆序对。如果周赛 514 中出现类似“交换相邻元素的最小次数”或“有多少对元素满足某种顺序关系”都可以转换思路。这类题通常不需要真的模拟交换只需要统计逆序对数量或满足条件对的数量。掌握逆序对的归并写法后再遇到按条件排序或比较两个子区间关系的题会更容易找到分治切入点。3.4 分治思路落地时先跑小数据再跑大数据分治代码不复杂但容易在边界、排序状态、统计时机上出错。落地时建议先跑三类数据最小规模数据比如长度为 1 或 2 的数组全逆序、全有序的数据随机数据。每次跑完都要把递归结果和暴力枚举结果对比避免用肉眼判断“大概正确”。这一条在周赛中特别实用因为周赛环境没有复杂的调试器很多时候只能靠打印日志。建议在关键函数入口打印left、right、mid和当前返回值如果问题出在递归过深打印次数明显不符合预期则优先检查出口或划分逻辑。4. 分治代码的通用骨架与示例4.1 归并排序模板的递归骨架以归并排序为例分治的递归骨架非常清晰。下面这段 Python 代码展示了划分、递归和合并三个阶段的顺序。def merge_sort(nums, left, right): if left right: return mid (left right) // 2 merge_sort(nums, left, mid) merge_sort(nums, mid 1, right) merge(nums, left, mid, right) def merge(nums, left, mid, right): tmp [] i, j left, mid 1 while i mid and j right: if nums[i] nums[j]: tmp.append(nums[i]) i 1 else: tmp.append(nums[j]) j 1 while i mid: tmp.append(nums[i]) i 1 while j right: tmp.append(nums[j]) j 1 nums[left:right 1] tmp这段代码的关键点是递归先拆到单元素单元素天然有序合并阶段用tmp接收两个有序区间最后回写到原数组。归并排序的时间复杂度是 O(n log n)空间复杂度是 O(n)因为每次合并都需要一个临时数组。实际周赛代码里可以在类内部维护一个全局tmp减少重复创建列表的开销。4.2 逆序对计算在合并阶段收集统计信息统计逆序对时只需要在归并排序的 merge 逻辑里增加一行统计。核心判断是当左半部分当前元素大于右半部分当前元素时左半部分从 i 到 mid 的所有元素都大于右半部分当前元素所以新增逆序对数量为mid - i 1。def merge_sort_count(nums, left, right): if left right: return 0 mid (left right) // 2 ans merge_sort_count(nums, left, mid) ans merge_sort_count(nums, mid 1, right) ans merge_count(nums, left, mid, right) return ans def merge_count(nums, left, mid, right): tmp [] i, j left, mid 1 count 0 while i mid and j right: if nums[i] nums[j]: tmp.append(nums[i]) i 1 else: count mid - i 1 tmp.append(nums[j]) j 1 while i mid: tmp.append(nums[i]) i 1 while j right: tmp.append(nums[j]) j 1 nums[left:right 1] tmp return count这里的常见错误是只在else分支里加 1但左半部分剩余的所有元素都大于当前右半部分元素正确的增量是剩余数量。另一个常见错误是在递归函数里重复统计左右区间内部逆序对。内部逆序对已经由两次递归调用返回merge_count只统计横跨中点的部分。4.3 最近点对分治合并阶段只关注边界带最近点对是一道典型的分治几何题。它的递归结构和归并排序类似按 x 坐标排序后分成左右两半递归求出左右两半内部的最小距离再在合并阶段检查距离中线足够近的点对。这个例子可以延伸出很多区间分治题的共同思路递归已经解决了子问题合并阶段只需要关注“跨边界”的部分。def closest_pair(points): points.sort(keylambda p: (p[0], p[1])) def solve(left, right): if right - left 3: # 小规模直接暴力 return min_dist_brutal(points[left:right]) mid (left right) // 2 mid_x points[mid][0] d min(solve(left, mid), solve(mid, right)) strip [p for p in points[left:right] if abs(p[0] - mid_x) d] strip.sort(keylambda p: p[1]) m len(strip) for i in range(m): for j in range(i 1, m): if strip[j][1] - strip[i][1] d: break d min(d, distance(strip[i], strip[j])) return d return solve(0, len(points))这个例子的合并阶段只处理 x 距离小于 d 的点然后按 y 排序。很多细节点需要专门调试递归区间切分时不能漏点strip 的过滤条件是abs(x - mid_x) d而不是 d处理边界时要避免比较同一个点的距离。最近点对并不是周赛高频题但它的合并思路对理解“边界带”非常有帮助。4.4 大数快速幂缩小规模但保持同构快速幂是最容易理解的分治例子因为它的递归逻辑非常直接求 a^n 时如果 n 是偶数就求 a^(n//2) 然后平方如果 n 是奇数还要额外乘一个 a。这里的子问题和原问题完全同构只是规模减半合并阶段是常数量级的组合。def pow_mod(a, n, mod): if n 0: return 1 if n % 2 0: half pow_mod(a, n // 2, mod) return half * half % mod else: half pow_mod(a, n // 2, mod) return half * half % mod * a % mod递归版的快速幂容易理解周赛和面试中也可以使用。如果担心递归栈压力可以把递归改成循环版。快速幂的复杂度是 O(log n)即使 n 是超大整数递归深度也只有几十层。从分治视角看快速幂是“划分最简单、合并最简单”的模板最适合用来检验自己对分治递归的理解。5. 周赛中的常见错误与排查清单5.1 递归出口遗漏导致栈溢出现象程序运行到一半直接栈溢出或者递归函数无限调用。检查方式在递归函数入口打印left、right或n观察是否出现相同参数重复打印。常见原因出口条件写成了left right但递归调用里可能传入越界区间导致永远不会走到出口。解决方案出口写成left right或者在递归调用前先检查参数范围。5.2 合并阶段漏掉跨区间的贡献现象排序或拆分结果正确但答案明显偏小比如逆序对统计结果为 0。检查方式单独构造只包含跨中点逆序对的数组比如 [2, 1, 3, 4]看合并且统计后是否产出 1。常见原因只递归计算了左右子区间没有在合并阶段统计横跨中点的贡献。解决方案在 merge 阶段明确区分“左右区间内部”和“跨左右区间”两部分内部结果由递归返回跨区间结果在合并阶段统计。5.3 划分不均匀导致复杂度退化现象小数据能跑通大数据严重超时。检查方式打印递归深度如果深度接近数组长度说明划分退化成链。常见原因快速排序选择了最坏 pivot或者划分时按值拆分布均匀。解决方案对数组类分治使用中点划分避免每次只分离一个元素对快排类算法使用随机化 pivot 或三数取中。5.4 误用分治却复用了错误的排序结果现象函数运行结果随机或依赖输入顺序。检查方式多次运行同一组测试数据看结果是否一致检查递归函数内部是否修改了原数组但没有在合并阶段回写。常见原因递归调用后子区间没有保持有序状态导致合并阶段的比较逻辑失效。解决方案在递归调用后插入临时打印确认子区间已满足排序或做预处理完成。5.5 分治调试清单调试分治代码时可以按这个清单逐项检查而不是盲目改代码。检查项检查方法处理建议递归出口最小规模输入是否返回正确基础值出口使用确保越界区间不会继续递归子问题边界左右区间是否有重叠或遗漏打印mid检查left..mid和mid1..right是否覆盖完整递归调用顺序merge 结果是否依赖调用后的数据状态确认子问题提前处理完毕再进入合并步骤合并阶段统计范围是否只统计跨区间贡献内部贡献交给递归合并函数只做跨区间统计排序状态合并前数据是否已具备有序条件用打印或单测确认子区间有序递归深度是否接近 O(n)检查划分是否均匀必要时增加 sys.setrecursionlimit 但要先确认复杂度大数据表现数据量 10^5 时是否超时或爆栈用随机数据与暴力方法对拍定位性能瓶颈6. 从周赛到面试分治怎么练才有效6.1 力扣刷题顺序里分治应该放在哪个阶段分治的练习应该建立在递归基础之上。如果递归调用还不熟练直接上归并排序和 CDQ 分治会非常吃力。推荐的练习顺序是先写简单递归比如二叉树遍历、快速幂再写归并排序和快排重点理解 merge 和 partition接着做逆序对、区间最大子段和、排序链表这类能复用模板的题最后再看整体二分、CDQ 分治和最近点对。力扣热题 100 里有不少题目看起来是链表、数组或树其实都可以用分治思想解决。比如合并两个有序链表、排序链表、将有序数组转换为二叉搜索树。刷这些题时不要只背代码要思考“这道题的子问题是什么合并阶段做了什么”。6.2 热题 100 与周赛题型的关系热题 100 更偏向面试常规题周赛题目则更强调时间压力和边界条件。两者对分治的要求不同。面试题允许慢慢推导递归式周赛需要在 10 到 15 分钟内识别出题型并写出代码。如果只在面试题库里刷很可能遇到周赛题时反应不过来因为周赛题很少直接写“请用分治”它会把分治藏在区间统计或排序优化的诉求里。另一个常见现象是选手刷了很多排序题但遇到“求满足条件的区间数量”时依然没有思路。原因是没有把排序、二分、分治连接成一条线。建议刷题时给自己加一道流程题“能在 O(n log n) 内统计数组中满足 nums[i] nums[j] 且 i j 的对数”。这道题打通了排序和分治的边界也是周赛里很多复杂题的基础。6.3 从一个题到一类题分治的四个练习方向第一个方向是排序模板包括归并排序、快速排序、链表排序。第二个方向是区间统计包括逆序对、区间最大子段和、区间满足条件对数。第三个方向是树形分治包括二叉树递归、表达式求值、从遍历序列构造二叉树。第四个方向是高级分治包括 CDQ 分治、整体二分、平面最近点对。对周赛选手来说前两个方向已经能覆盖大部分分治题。第三个方向更多出现在二叉树和递归题里第四个方向通常不会作为周赛压轴但如果掌握了对理解复杂区间问题会有很大提升。建议每周挑 2 到 3 道分治相关题目用同一套模板反复练习直到能不看题解写出归并逆序对代码。6.4 周赛复盘时给每道题标注分治落点周赛结束后的复盘比比赛本身更重要。每次复盘时不要只记录“这题不会”而是把每道题的核心算法标出来问自己三个问题这道题能拆成同构子问题吗拆分后能直接合并答案吗如果能合并阶段做了什么即使题目答案是贪心或动态规划也值得分析它为什么不是分治。长期坚持这个习惯会对“什么题该用分治”形成很强的直觉。这种直觉在限时赛里尤其重要因为分治题一旦识别成功代码结构基本固定剩下的只是边界和细节。下次再遇到区间、配对、排序相关题目时会自然进入“划分、治理、合并”的思考流程而不是靠试错碰运气。真正把分治练熟不是记住几个模板而是能在看到题目时快速判断它的子问题结构并且回到“划分、治理、合并”三个环节去验证。建议从归并排序开始每天写一遍逆序对代码再做两到三道区间统计题每周周赛复盘时简单画出每道题的子问题和合并路径。坚持一段时间后分治会从一个需要刻意记忆的算法变成一种顺手的思维工具。