P3396 哈希冲突 分析 & 根号分治

· · 个人记录

根号分治是一种暴力的算法：将问题以 \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 级别，可以通过。

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