根号分治思想入门

_Fireflies_ · 2026-06-17 20:51:08 · 算法·理论

::::warning[注意]{open}

对于本文标有例题字样的题目，可以跟随笔者的思路一起思考，而对于本文标有练习字样的题目，建议先跟随笔者的提示自行思考后再查看详解。

::::

引入：

根号分治是一种优美的分治思想，更是 OI 中一个重要的 trick，能够融入进各种题目之中达成出其不意的效果，也能将一个极其复杂的题目简化为简单的暴力拼接，非常值得学习。

分治分治，顾名思义就是分而治之，一个问题往往有多种解决方法，它们的复杂度也不尽相同，那我们能不能将几个单独都无法通过的暴力做法通过一些组合，分治将其变为可以通过的做法呢？

这时就可以使用根号分治的思想，例如某一问题有两种做法，做法一复杂度 O(k) 而做法二是 O(\frac{n}{k})，两者若单独使用都能够造数据使其退化为 O(Qn)，但是我们可以利用它们的性质，k 越大时，做法二越优秀，k 越小时，做法一越优秀。

所以我们就可以对 k 设置一个阈值 B，在 k>B 时使用算法二，否则就使用算法一，这时的单次操作复杂度就被我们优化为 O(B+\frac{n}{B})，这个时间复杂度取决于我们设置的阈值 B，利用基本不等式得 B+\frac{n}{B} \ge 2 \sqrt{n}，取等条件为 B=\sqrt{n}，所以设置阈值 B=\sqrt{n} 就可以得到理论最优复杂度 O(Q \sqrt{n})，这可比暴力的 O(Qn) 快了整整 \sqrt{n} 倍！

入门：

我们提到根号分治思想可以融合进许多题目之中，接下来就会展示一些较为简单的结合方式。

::::info[例题一：CF1207F Remainder Problem]{open}

CF1207F Remainder Problem，难度绿。

题意：

有一个长度为 5\times 10^5 的数列，下标从一开始，初始都为 0，n 次操作，操作为单点加或查询序列中所有下标模 x 等于 y 的元素之和。\ 数据范围 n,x,y \le 5 \times 10^5，时限四秒。

根据我们刚才所提的，根号分治思想是通过在不同情况下将数据分给不同复杂度形式的暴力来实现对单一暴力算法的优化的，那么请读者先思考几种暴力做法。

:::info[暴力其一] 直接按题意模拟，单点加 O(1)，查询 O(n) 跑一遍序列，总复杂度 O(n^2)。 :::

:::info[暴力其二] 维护所有模 x 余 y 的元素之和，即预处理答案数组，查询时直接查表，由于每次修改受影响的答案数组元素数量是 O(x)=O(n) 量级的，故复杂度 O(x^2)=O(n^2)。 :::

看起来两个暴力毫无关联？仔细想想它们复杂度的性质。

这时我们发现：暴力一在 x 较大时比较快，即实际上的单次询问复杂度是 O(\frac{n}{x}) 的；暴力二则需要 x 小才快。

所以这就可以按 x 分治了，设置阈值 B。