概述
-
根号分治,是一种对数据进行分治的分治方式。
-
具体来说,如果所要求进行的过程满足如下性质:
-
根号以下的数据的种类很少,可以全部维护之;
-
根号以上的数据,直接暴力的复杂度可接受。
-
-
那么可以考虑使用根号分治。
-
通常根号分治往往和数论上的小质数、大质数(以根号为界)的性质相关,例如 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})\)。