本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-11 11:10:53

根号分治是一种暴力的算法：将问题以 $\sqrt{n}$ 为界，使用两种不同的算法，达到较好的复杂度。

对于本题，我们如果纯使用暴力来做，那么代码类似于：

查询：

int x, y, res = 0;
...
for (int i = y; i <= n; i += y) res += a[i];

修改：

seq[x] = y;

查询是 $O(n)$ 的，而修改 $O(1)$。整体复杂度就是 $O(nm)$，显然不行。

我们容易发现：当 $y$ 很小的时候，查询的操作数多；当 $y$ 很大的时候，操作数反而少了。因此我们可以想到这样的策略：当 $y$ 小的时候我们预处理出值，当 $y$ 大的时候，我们暴力。修改的时候，我们更新预处理出的值。

分界线是什么呢？明显是使得两边复杂度都最小的值，就是 $\sqrt{n}$。此时，小规模查询的复杂度是 $O(1)$，大规模查询的复杂度是 $O(\sqrt n)$，修改的复杂度是 $O(\sqrt {n})$，整体复杂度是 $O(m\sqrt n)$，大约是 $10^8$ 级别，可以通过。

这就是根号分治，是一种“分而治之”的思想。