分治

ty_mxzhn · 2026-02-12 14:38:29 · 算法·理论

不得不说写的真的不好，分治这个东西道理我觉得目前还不是很足。

大概也就分几类：点分治，归并，等价类分治，线段树分治，整体二分，CDQ 分治。

有没有人告诉我怎么写的更好。

1 分治

1.1 分治概述

分治有很多种，可以按照很多方法分类，这里乱序讨论几种。

1.2 点分治

形式化的定义是：在一个图上抽取一些关键元素，统计所有经过关键元素的路径信息，然后分解为若干个子问题。

有如下几种：“猫树分治”，“树上点分治”，“网格图分治”，“最值分治”。

特点为：无需 pushdown，无需 pushup。

算法流程如下：

1. 处理点集 S 内路径 (u,v) 相关的答案。
2. 找到 S 中的一个点集 rt。
3. 处理所有跨过至少一个 rt 内的点的路径。
4. 删去 rt 内所有的点并递归到连通块。

Travel around China

考虑分治，选择一列并分割，则两边的点想要互相到达一定要经过这一列点。

每层只有 d_{i,0},d_{i,1},d_{i,2} 三种信息，表示到达三种中心的最短距离。

钦定某种信息最大，剩下两个信息比这个信息小的限制是二维偏序，于是我们做到每层时间复杂度 O(n\log n)。则总时间复杂度 O(n\log^2 n)。

Quick Tortoise

每次选择一行或者一列作为分治中心，处理跨过分治中心的查询。使用 bitset 优化转移，判定时取交。

复杂度 O(\dfrac{n^3\log n}{\omega}+n^2\log n)。

rprmq1

考虑按照纵坐标分治，处理跨过 y=mid 这条直线的所有查询。

在线段树上，区间加，查询历史最值即可。

永恒

非常好的题。

树上问题，做点分治，首先处理跨过 u 的所有查询。

对于一个点对 (x,y)（注意这是查询时枚举的那两个点），其可以贡献到 x 的子树内的查询 u 和 y 子树内的查询 v。其权值为在第二颗树上 lca 的深度。

处理 lca 深度，类似那个叫做 LCA 的题。考虑构建 x 到根的加 1，查询 y 到根的和。

如果我们有关于 x 和 y 的权值（也就是第一颗树上的子树大小）也是同理的。

对此问题，由于离线，可以在第二棵树上面构建虚树，从下往上做前缀和处理到根的 +1，和从上往下做前缀和处理到根的查询即可。

成都七中

点分治。

关键性质：若 x 可以到达分治中心，则令 x 为分治中心即可。

递归下去时把已经可以挂到分治中心上的询问删去。

接下来，为了求出颜色数，只需要做一个二维偏序。修改 O(n\log n) 次，查询 O(q) 次。如果愿意的话也可以平衡。

如果你看不懂，看下面的题解。

一千年以后

这不是正解。2log 是什么梗。

点分治，我们定义一个连通块的代表元为其在点分树上深度最小的点。不难发现这是唯一的。

在代表元处处理颜色贡献。我们发现一个点被纳入连通块的条件为 (l,r)，其中若查询是 L,R 那么 L\le l\le r\le R。

考虑数颜色，同种颜色的点单独拿出来，按照 l 排序。

现在我们让 l 最大的那个点成为一种颜色的代表元。

那么对于每个区间成为代表元的条件，首先这个区间不能包含别的区间，然后限制大概长这样：

是一个二维偏序，如果容斥掉这个点分治的根不是代表元这个条件的话就是一些二维偏序。

最后数点就好了，2log。

Min+Sum

最值分治，找到最小值的位置 p 并处理。则所有跨过 p 的区间的最小值一定为 p。

暴力做是不行的，只需要枚举较小的一边即可。类似启发式合并的实现，复杂度为 O(n\log^2 n)。如果用猫树分治可以做到同一个复杂度，在此不做展开。

stcm

考虑使用 dfs 序进行构造。只需要构造出 [dfn_i,dfn_i+siz_i-1] 这个区间的补即可。

分治。每次处理到分治区间 [l,r] 时，保证当前信息为 [l,r] 的补。

考虑处理所有跨过 mid 的查询。由于树结构拍到 dfs 序上后一定也只会有相离和包含两种区间关系，那么所有跨过 mid 的查询两两包含。

所以我们可以 lp\to mid\leftarrow rp 这样一次把指针扫到中间，并处理所有跨过 mid 的查询。

撤销后继续递归即可。构造复杂度 O(n\log n)。

我觉得有必要用二维平面来描述这个构造，但是由于“只有相离和包含两种区间关系”不是很好刻画就摆了。

1.3 归并

这个很形象，就是只解决一个问题，通过分而治之的思想解决。

比如用结合 FFT 计算 n 个低次多项式的乘积和归并排序。在此不做过多展开。

2 等价类

2.1 定义

问题：给你 q 个询问集合 S_1,S_2,...,S_q\subseteq 2^{\{1,2,...,n\}}。S 有性质。查询 f(S_i)=\displaystyle \prod_{j\in S_i} a_j。其中 a 的类型是任意一种满足结合律的信息。

等价类分治的算法流程如下：

1. 对于所有询问集合 S_1,S_2,...,S_q，找出每种本质不同的 S_{i,U}=S_i\cap [l,r]。这个集合的种数不超过量级 f(r-l)。
2. 处理 [l,mid] 与 [mid+1,r] 中，每种等价类的答案。例如定义 S_{i,L}=S_i\cap [l,mid] 则求出 f(S_{i,L})。
3. 合并得到 f(S_{i,U})=f(S_{i,L})f(S_{i,R})。
4. 总复杂度 T(n)=O(f(n))+2T(\dfrac{n}{2})。

可以结合分块，每块内再进行分治。

若块长为 B，则总复杂度为 O(\dfrac{nq}{B}+\dfrac{nT(B)}{B})。

可以发现，等价类分治按照分治结构分类的话，实际上是一种归并。

好像有个东西叫做 TB5 分治。但是我还没学。

2.2 应用

例题：D2T2。查询序列 a 只保留区间 [l,r] 中，值域为 [L,R] 的数后拼起来的序列的最大子段和。

对原序列做序列按照 B 分块。对一个块内的数，如果查询整块，其最多有 B^2 种本质不同的查询。也就是说等价类有最多 B^2 个。预处理即可快速查询。

对于块内等价类的预处理，考虑分治，算出两半的等价类信息后，暴力查表找出新的等价类信息。这样复杂度为 T(n)=2T(\dfrac{n}{2})+O(n^2)，有 T(n)=O(n^2)。

设 B=\sqrt{n}，复杂度为 O(n\sqrt{n})。

3 线段树分治

3.1 思想

线段树分治是一种奇特的分治。

首先我们要对于每个 x 询问区间 l\le x\le r 的信息的并。

为此我们先把区间拆成 \log 个线段树上的区间。分治流程如下：

1. 加入这个节点 [l,r] 上的所有区间信息。
2. 递归 [l,mid] 和 [mid+1,r]。
3. 撤销这个节点 [l,r] 上的所有区间信息。

此时每个 x 收到的贡献是它的祖先节点上的所有贡献。

3.1 城市建设

很经典的线段树分治。考虑区间 [l,r] 内“将要加入”的边。也就是线段树上一个点的子树。假设这些边为“关键边”。

首先将关键边的边权设为 -\inf，此时就在 MST 中的非关键边一定在区间 [l,r] 内 MST 的答案中。用并查集合并这些点。

然后将关键边的边权设为 \inf。此时不在 MST 中非关键边一定不在区间 [l,r] 内 MST 的答案中。可以筛去这些边。

这样我们让分治下去的边数和点数都控制在 O(r-l) 内。

所以这大概是一道结合了一点等价类思想的线段树分治题。但是只是看起来像等价类思想，这个算法流程完全不一样。

3.2 最短路径

模板题，定义 s_{[l,r]} 表示 [l,r] 的补的两两最短路信息。不需要撤销，只需要暴力计算 s_{[l,mid]},s_{[mid+1,r]} 即可。复杂度 O(n^3\log n)。

4 整体二分

4.1 思想

思想：对于要对 q 个询问分别二分的问题，考虑维护一个集合 S_{[l,r]} 表示答案在 [l,r] 中的集合，这样一共有 O(n) 个区间，每个区间到下一个区间的信息以复杂度 O(r-l) 变化，总变化量 O(n\log n)。

其特征为：不同二分问题所需的贡献有大量重叠。

4.2 I 君的探险

需要更多的限制：保证没有孤立点。

考虑树的部分分。我们要确定每个点的父亲。

整体二分，点亮左半边的点，可以判定右边所有点的父亲是否在左半边内。如果不在，则递归到右边，否则是左边。

考虑一般情况，此时若随机打乱点，并跑上面的算法，每次期望删除 \dfrac{m}{3} 条边，然后再判断是否这些点已经删完即可。

4.3 Best Subsequence

先二分一个 w，将序列中的元素分成 \le \dfrac{w}{2} 和 >\dfrac{w}{2}。

则任意两个小元素之间不会爆限制，两个小元素之间可能可以选一个大元素，但不能选两个大元素，因为这两个大元素就会爆限制。

性质：每个小元素都会被选。证明考虑调整法，如果两个小元素之间选了大元素，并且还有中间还有小元素没选则可以把选大元素换成选那个小元素。于是查询最小值可以计算任意两个小元素之间的最小元素。

整体二分，此时小元素和大元素之间有转变，可以用数据结构带 log 维护。总共复杂度 2log。

4.4 静态决策单调性优化

设区间 [L,R] 选择的决策点区间为 [l,r]。

快速求出 mid=\lfloor\dfrac{L+R}{2}\rfloor 的决策点 m。则递归到 [L,mid-1],[l,m] 和 [mid+1,R],[m,r]。

5 CDQ 分治

5.1 思想

大概是左中右的顺序：先处理左侧，然后左贡献右，然后处理右边。

5.2 Druzyny

分治优化 dp 模板题。

如果我们要从 j 转移到 i，则限制为：j-i\in \bigcap_{k=j+1}^i [l_k,r_k]。

考虑 CDQ 分治。

先处理左侧的贡献，然后处理左贡献右，最后处理右边。

左贡献右的问题可以这么看：