概述
-
根号分治，是一种对数据进行分治的分治方式。
-
具体来说，如果所要求进行的过程满足如下性质：
-
根号以下的数据的种类很少，可以全部维护之；
-
根号以上的数据，直接暴力的复杂度可接受。
-
-
那么可以考虑使用根号分治。
-
通常根号分治往往和数论上的小质数、大质数（以根号为界）的性质相关，例如 func 那道题，故也许也可以叫数论分治。
-
一定程度上，根号分治也是一种数据分治，只不过不是数据点分治罢了（笑）。
P3396 哈希冲突
-
题意：给定序列 \(a_{1\sim n}\)，有 \(m\) 个操作，为单点修改或求 \(\sum\limits_{i\bmod p=x} a_i\)。
-
数据范围：\(n,m\leqslant 1.5\times 10^5,p<n\)。
-
注意到传统方法，譬如线段树和分块，都不能很好地处理 \(\bmod p=x\) 的和，究其原因是 \(p\) 太多了，不同的 \(p\) 之间又互相难以复用。
-
但观察到对于大数即 \(\geqslant \sqrt{n}\) 的 \(p\)，直接暴力的复杂度是 \(O(n\sqrt{n})\)。
-
于是考虑根号分治，小数只有 \(O(\sqrt{n})\) 个，修改时直接暴力修改。
-
总复杂度 \(O(\sqrt{n})\)。