根号分治

标签：10 le dfrac 复杂度 分治 根号

前言

因为觉得这个思想很有意思，最近也见到了许多使用根号分治的题目，自己也出了一些用根号分治的题目，所以想总结一下。

（下文各种根号分治的名字是我掰出来的，应该有别的称呼）

对文章的细节有疑问或是发现错误的欢迎提出。

介绍

根号分治是一种在对数据规模分类讨论的基础上利用不同算法平衡复杂度的思想。

根号分治的思想非常朴素，举个例子：

对于一个 \(n\le 10^9\) 的题目，小明想出了一个能过 \(n\ge 10^4\) 的暴力，小红想出了一个能过 \(n\le 10^4\) 的暴力，那么如果他们开黑，将这两个暴力合在一起过了题，那么我们就可以说他们使用根号分治通过了这道题，是一种优秀的做法。

从上例可以看出，根号分治的重点在于分治，而不是根号，根号只是在部分情况下复杂度的形式。

根号分治的本质是平衡复杂度，这里的复杂度包括时间复杂度和空间复杂度，根号分治可以实现时间和空间之间的转化。

根号分治有一个重要特点：和一定。这里的和的类型多种多样，比如字符串的长度和，点的度数和，点对的距离和等等。

因为和的类型多种多样，因此根号分治的应用场景十分广阔。（为什么什么东西都能根分）

接下来你将会见到一些不同类型根号分治的基础应用和扩展应用。

应用

度数根号分治
给出一张 \(n\) 个点，\(m\) 条边的无向图，每个点有点权，进行 \(q\) 次操作，操作分两种：

• 将点 \(x\) 的点权增加 \(k\)。
• 查询与点 \(x\) 直接相连的点的点权和。
  \(1\le n,m,q \le 10^5\)。

这道题可以说是根号分治最经典的题目之一了，我们按照根号分治的过程分析。

首先，我们需要找到一个东西，满足它的和一定，在这道题中，我们发现给出的是一个一般无向图，没有什么好的性质……吗？

因为边数为 \(m\)，一条边会使得其两个顶点的度数增加 \(1\)，因此所以点的度数和是 \(O(m)\) 的！

那么我们考虑根据点的度数进行根号分治，按照套路，设定一个阈值 \(B\)，我们将点按度数大小分为 \(\ge B\) 和 \(< B\) 两类，分别称为重点（大度数点）和轻点（小度数点）。

因为点的度数和为 \(m\)，因此我们发现一个重要性质：重点的个数不会超过 \(\dfrac{m}{B}\)，这也是根号分治最重要的性质，即在确定阈值后，大于阈值的个数不会超过数据规模与阈值的比。

我们对于每个重点都维护与其直接相连的点的点权和，记做 \(v\)，接下来对操作和点的类型分类讨论：

• 操作 \(1\)：

直接将点 \(x\) 的点权加 \(k\)，并扫一遍与 \(x\) 直接相连的重点 \(y\)，更新 \(v_y\)。

• 重点操作 \(2\)：

直接输出 \(v_x\)。

• 轻点操作 \(2\)：

暴力扫一遍所有与 \(x\) 直接相连的点，计算答案。

分析一下复杂度，单次第 \(1\) 类的时间复杂度是 \(O(\dfrac{m}{B})\) 的，因为重点个数是这个级别，对重点操作 \(2\) 是 \(O(1)\) 的，对轻点操作 \(2\) 是 \(O(B)\) 的，因为轻点的度数不会超过 \(B\)，因此，总时间复杂度为 \(O(qB+q\dfrac{m}{B})\)，根据我们小学二年级学习的均值不等式，当 \(qB=q\dfrac{m}{B}\)，也就是 \(B=\sqrt m\) 时时间复杂度取到最小值，最小值为 \(O(q\sqrt m)\)。

我们说了这么久的根号终于出现了！

时空平衡根号分治
有 \(n\) 个集合，集合中元素个数和为 \(m\)，进行 \(q\) 次询问，每次询问两个集合交集的元素个数。
\(1\le n,m,q\le 10^5\)。

我们都知道有一个东西叫做 bitset，我们直接开 \(n\) 个大小为 \(m\) 的 bitset，对于一个集合，若一个数存在，那么对应位就是 \(1\)，否则是 \(0\)。

在询问时，我们直接将这两个询问的集合的 bitset 与一下，再数一下 \(1\) 的个数就可以了。

让我们看看复杂度，时间复杂度是 \(O(\dfrac{nm}{w})\) 的，可以通过，但空间复杂度是 \(O(nm)\) 的……

我们发现 bitset 中的 \(1\) 相当稀疏，空间浪费的很严重，怎么办呢？根号分治！

套路的，设定阈值为 \(B\)，我们只对所有元素个数 \(\ge B\) 的集合开 bitset，那么 bitset 的个数不会超过 \(\dfrac{m}{B}\)，这样空间就可以接受了。

询问时，我们将元素个数小于 \(B\) 的集合中的元素先放入一个公用 bitset 中，再与另一个集合的 bitset 与。

那么这样操作下来，时间复杂度变成了 \(O(qB+\dfrac{nm}{w})\)，空间复杂度是 \(O(\dfrac{nm}{B})\)，当 \(B\) 取一个合适的值的时候就可以通过了。

从这个例子中，我们看出了根号分治平衡时空复杂度的强大能力。

分类根号分治
统计 \([l,r]\) 中满足以下条件的数的个数：

• 数位中含有 \(k\) 个连续的数字 \(b\)。
• 可以被 \(x\) 整除。
  多测，\(1\le l \le r\le 10^{11},1\le x\le 10^{11},1\le T\le 10\)。

（所谓分类根号分治，就是 暴力 + 暴力 = 正解）

就跟我们在文章开头举的例子一样，我们设定一个阈值 \(B\)，当某个数据范围小于 \(B\) 时我们使用一种暴力，否则使用另一种暴力。

当 \(x \ge B\) 时，我们发现可以暴力枚举 \(x\) 的倍数并暴力判断是否合法，时间复杂度为 \(O(T\dfrac{V\log V}{B})\)，其中 \(V=10^{11}\)。

当 \(x < B\) 时，我们考虑数位 DP（这个问题看起来就很数位 DP 不是吗）。

设计函数 dfs(pos, limit, have, rem, cnt) 表示当前考虑到第 \(pos\) 位，是否紧贴上界（\(limit\)），是否符合有 \(K\) 个 \(B\) 的条件（\(have\)），当前对 \(X\) 的余数为 \(rem\)，当前已经有 \(cnt\) 个连续的 \(B\) 的方案数，直接记搜即可。

具体的说，考虑记忆化数组 \(f_{pos,have(0/1),rem,cnt}\)，转移为

\[f_{pos,have,rem,cnt}=\sum_{o=0}^{up}\begin{cases}f_{pos-1,have\lor[(cnt+1)\ge K],(10rem+o)\bmod X,cnt+1}&o=B\\f_{pos-1,have,(10rem+o)\bmod X,0}&o\not =B\end{cases} \]

其中，\(up\) 表示当前的数位上限，当 \(limit\) 为 \(1\) 时其值为当前 DP 上界的十进制表示的第 \(pos\) 位，否则为 \(9\)。

时间复杂度为 \(T\times O(B\lg^2V)\times O(\lg V)=O(TB\lg^3 V)\)。

那么我们的总复杂度就是 \(O(T(\dfrac{V\lg V}{B}+B\lg^3 V))\)，还是使用均值不等式，得出当 \(B\) 取 \(\dfrac{\sqrt V}{\lg V}\approx28,748\) 时最优，为 \(O(T\sqrt V\lg^2V)\approx 4\times 10^8\)，由于常数比较小所以可以通过。

空间复杂度为 \(O(B\lg^2V)=O(\sqrt V\lg V)\approx 3.5\times 10^6\)，可以接受。

事实上，分类根号分治是最常用的根号分治方法之一，平衡两种暴力的复杂度的思想是非常重要的。

本质上，分类根号分治利用的是数据范围的和一定的性质。（这也算性质）

余数根号分治
维护一个长为 \(n\) 序列 \(a\)，进行 \(q\) 次操作，操作分以下两种：

• 将 \(a_x\) 增加 \(k\)。
• 查询所有下标模 \(x\) 的余数为 \(k\) 的所有数的和。
  \(1\le n,q\le 10^5\)。

（事实上，这个类别应该归入分类根号分治中，但因为比较常见就单独拎出来了）

因为这也是分类根号分治的一种，因此我们考虑两种暴力：

• 直接修改，查询时从 \(k\) 开始枚举，每次 \(+x\)，求和。

• 设 \(f_{i,j}\) 表示下标模 \(i\) 的余数为 \(j\) 的所有数的和，修改时 \(O(n)\) 更新 \(f\) 数组，查询时直接查表输出。

我们发现，这两种暴力分别对应了两种极端：一种是 \(O(1)\) 修改，\(O(n)\) 查询，另一种是 \(O(n)\) 修改，\(O(1)\) 查询。

那么我们还是按照老套路，将这两种暴力合并。

设定阈值为 \(B\)，对应 \(x>B\) 的查询我们直接按照做法 \(1\) 的做法暴力做，时间复杂度为 \(O(q\dfrac{n}{B})\)。

同时，我们依旧开一个表，但我们只开 \(B\times B\) 大小的，也就是说，设 \(f_{i,j}\) 表示下标模 \(i\) 的余数为 \(j\) 的所有数的和，其中 \(j\le i \le B\)。那么对于 \(x\ge B\) 的查询我们依旧可以查表，这样查询就搞定了。

修改时，因为我们只开了 \(B\times B\) 的表，因此单次改表的复杂度是 \(O(B)\) 的。

算下来，总时间复杂度为 \(O(q(B+\dfrac{n}{B}))\)，空间复杂度为 \(O(B^2)\)，容易得到当 \(B\) 取 \(\sqrt n\) 时复杂度最优，为 \(O(q\sqrt n)\)。

模根号分治常见于数据结构题中，跟下文的步长根号分治有一定的相似性。

颜色根号分治
给定一个 \(n\times n\) 的网格，每个点有一个颜色 \(a_i\)，统计有多少条路径满足以下条件：

• 起点和终点的颜色相同。
• 只能向下或向右走。
  \(1\le n\le 500,1\le a_i\le n^2\)。

首先，我们需要找到和一定的东西，在颜色根号分治中，和一定的是点的数量（这不是废话吗），或者换句话说，是所有颜色的点的数量和。

先别管那么多，我们设定阈值为 \(B\)，如果某种颜色的点的数量大于 \(B\)，那么我们将这种颜色称为重颜色，否则称为轻颜色。我们容易发现，重颜色的种数不会超过 \(O(\dfrac{n^2}{B})\)。

对于这道题，我们对每种颜色独立考虑，对当前考虑的颜色是轻还是重分类讨论。

• 如果当前是轻颜色，那么我们直接双重枚举该颜色的所有点，对于一对点 \((x_1,y_1),(x_2,y_2)\)，其能产生的路径数量显然是 \({x_2-x_1+y_2-y_1\choose x_2-x_1}\)。

• 如果当前是重颜色，我们发现还有一种 DP 做法可以统计路径数量。

设 \(f_{i,j}\) 表示以 \((i,j)\) 结尾的路径数量，那么有：\(f_{i,j}=f_{i-1,j}+f_{i,j-1}+a_{i,j}\)，其中，\(a_{i,j}\) 在点 \((i,j)\) 的颜色时当前颜色时其值为 \(1\)，否则为 \(0\)。

分析一下复杂度，重颜色的数量不会超过 \(\dfrac{n^2}{B}\)，对于每一种重颜色我们都做一遍 \(O(n^2)\) 的 DP，这部分的复杂度是 \(O(\dfrac{n^4}{B})\)。

轻颜色的数量是 \(O(n^2)\) 级别的，而轻颜色的点的数量是 \(O(B)\) 级别的，看似总复杂度为 \(O(n^2B^2)\) 的，但考虑到一个点最多被枚举 \(B\) 次，因此这部分的复杂度实际上是 \(O(n^2B)\)。

那么总复杂度是 \(O(n^2B+\dfrac{n^4}{B})\)，还是用熟悉的均值不等式，得出当 \(B=n\) 时复杂度最优，时间复杂度为 \(O(n^3)\)。

颜色根号分治也是常见的根号分治，经常会结合一些奇怪的东西一起考察。

步长根号分治
给定一颗 \(n\) 个点的带边权树，边权为 \(1\) 或 \(2\)，多次询问，问在从点 \(u\) 出发到点 \(v\)，一次可以走 \(k\) 的距离的情况下最少要走几步。
\(1\le n\le 10^5,1\le k\le n\)。

步长根号分治利用的是两点之间距离一定的性质。

设定阈值为 \(B\)（万能的套路），那么我们发现当 \(k> B\) 时，我们最多跳 \(\dfrac{n}{B}\) 步，而跳一步可以用树剖 + 二分实现（找到最后的重链，在重链上二分，需要预处理距离），是 \(O(\log n)\) 的，这部分的时间复杂度为 \(O(nB\log n)\)。

当 \(k\ge B\) 时，我们预处理 \(f_{i,c,j}\)，表示从点 \(i\) 出发，在一次跳 \(c\) 的距离的情况下跳 \(2^j\) 次步跳到的点。

这个东西可以之间倍增处理，也就是 \(f_{i,c,j} = f_{f_{i,c,j-1},c,j-1}\)，而 \(f_{i,c,0}\) 可以用上述所说的树剖 + 二分求出。

那么单次询问时我们从 \(u,v\) 分别往上倍增跳，跳到不超过其 LCA 的最远点，再判断一下最后的距离要跳一次还是跳两次即可。

步长根号分治可以看作余数根号分治的扩展。不过做法的细节还是比较多的。

总结

除了上述几大类根号分治之外，还有一些比较特别的根号分治，比如质因子根号分治，斜率优化根号分治等等，但因为泛用性不广，故不一一列出。

总的来说，根号分治是一种常见的思想，在 OI 中占有一席之地，在遇到可以找出某个东西和一定的题目时可以想想根号分治。

涉及到平衡复杂度的算法并不多，主要就是一众根号算法（根分，分块，莫队），当复杂度不平衡时可以往这边想一想。

更多题目

（包括了上面的一部分题目，还有一些其他题目，都是洛谷链接，有些题是 OJ 的内部题放不上来）

步长根号分治：ODW。

颜色根号分治：Regions，Frequency Problem，Yet Another Path Counting。

余数根号分治：Remainder Problem。

分类根号分治：Two Arithmetic Progressions，9，Train Maintenance，You Are Given a Tree，Array Queries。

度数根号分治：交友问题。

标签：10,le,dfrac,复杂度,分治,根号
From： https://www.cnblogs.com/TKXZ133/p/17772749.html