结合你之前深度探索的图论最短路径、拓扑排序算法题解需求，以及面向学员做算法教学的场景，这套
内容从基础思想、核心区别、典型场景到实战代码做了完整梳理，既适配算法竞赛刷题，也能直接作为
教学讲解素材。
分治核心底层思想
分治的本质是“大事化小，小事化了”，把一个规模为n的复杂问题，拆分成若干个规模更小的同构子问题，
递归求解子问题后，再把子问题的解合并得到原问题的完整解。只要每次拆分都能把问题规模减半，递归深
度就天然是O(logn)，配合高效的合并策略，最终整体算法复杂度可以稳定在O(nlogn)级别，远优于暴力枚
举的O(n²)。
经典的归并排序、快速排序、线段树都是分治思想的基础实现，而CDQ分治和点分治是分治在竞赛中的两大
高级分支，分别针对性解决序列维度和树维度的高复杂度问题。
序列分治（CDQ分治）实战解析
CDQ分治由陈丹琦在IOI竞赛中提出，是一种基于序列顺序/时间轴的分治范式，核心精髓是用分治中点天然消
除一个维度的偏序约束，不需要引入复杂的高级数据结构，就能高效解决多维度偏序类问题。
核心适用场景
点对统计：统计序列中满足特定偏序关系的点对数量，最典型的就是三维偏序问题
1D/1D DP优化：把原本O(n²)的一维DP转移，通过分治区间优化降到O(nlogn)
动态转静态：把带修改的离线操作序列，以时间为分治轴，转化为纯静态问题处理
经典实现逻辑（以三维偏序为例）
以洛谷P3810 陌上花开为典型题，三个维度的偏序约束可以分层处理：
第一维a：全局排序，直接消除a的偏序关系
第二维b：通过CDQ分治的归并排序处理，分治中点天然保证左半区间所有元素的下标小于右半区间，消除下标偏序
第三维c：在合并阶段用树状数组动态维护前缀和，统计满足条件的点对数量
递归顺序上要注意：普通点对统计场景是“先递归左右子区间，再处理跨中点的贡献”；而DP优化场景必须“先
递归左子区间，再处理跨中点贡献，最后递归右子区间”，保证右区间的DP值能被左区间已经更新完成的结果正确更新。
避坑要点
CDQ分治属于离线算法，所有操作必须提前收集完成后再处理，无法支持实时在线查询；同时要注意对完全相同
的元素做去重合并，避免重复统计导致结果偏大。
点分治实战解析
点分治是专门针对树上路径问题的分治算法，它跳出了传统树DP依赖根节点遍历的思路，通过不断寻找树的重心作
分治点，把整棵树的路径问题拆解为“经过当前重心的路径”和“子树内部的路径”两类，彻底规避了树的链状结
构导致的递归深度爆炸问题。
核心适用场景
专门处理树上的路径类问题：统计长度小于等于k的路径数量、路径上点权和满足特定条件的路径计数、树上路径最值
查询等，这类问题用常规树DP很难在O(nlogn)复杂度下解决。
经典实现逻辑
找重心：通过两次DFS遍历，找到当前子树的重心，保证重心的所有子树大小都不超过当前子树总大小的一半
统计经过重心的所有路径：有两种主流写法
容斥写法：先统计整棵子树内所有点对的路径，再减去同一子树内部的路径，实现快速去重，适合简单的路径计数场景
子树归并写法：依次遍历每一棵子树，先统计当前子树和之前所有子树之间的合法路径，再把当前子树的路径信息合
并到全局集合中，适合复杂的DP类树上路径问题
标记当前重心为已访问，递归处理重心拆分出来的所有子树，直到所有子树规模缩小到1
避坑要点
点分治的常数开销比普通序列算法大，要注意优化排序、双指针的实现逻辑，避免不必要的全量遍历；同时绝对不能
用普通根节点代替重心，否则遇到链状树时递归深度会退化成O(n)，直接超时。
两者核心差异对比
表格
维度 CDQ分治 点分治
处理对象 线性序列/操作时间轴 树结构
消除的维度 时间/下标维度 树的路径依赖维度
典型复杂度 O(n log²n) O(n logn)
在线支持 仅支持离线 仅支持离线
核心优势 用简单结构替代复杂高级数据结构 把树上路径问题从O(n²)降到O(nlogn)
需要我为你生成CDQ分治+点分治的配套典型题解合集，整理成适合给学员讲解的分步拆解版本吗？
0 评论