基本技巧——根号分治 学习笔记
根号分治与其说是一个算法，更不如说是一种思想（trick）。
定义
根号分治，是一种对数据进行点分治的分治方式，它的作用是优化暴力算法；类似于分块，但应用范围比分块更广。
具体来说，对于所进行的操作，按照某个点 \(B\) 划分，分为大于 \(B\) 及小于 \(B\) 两个部分，两部分使用不同的方式处理。（一般以根号为分界，即 \(B = \sqrt n\)，因为这样复杂度最平衡）
简而言之，根号分治就是：对数据范围分块处理，将多个暴力算法“拼接在一起”，实现优化复杂度的作用。
算法思路
理论基础
具体思路如下：
- 对于数据的种类少的部分，可以全部维护；
- 对于另一部分，不方便维护的，可以暴力求解。
题目特征
- 能将原问题分为一个大问题（即前文说的 \(>\sqrt n\)）和一个小问题（即前文说的 \(<\sqrt n\)）；
- 小问题的情况不多，可以维护所有可能的答案或用离线算法求解；大问题可以用暴力求解；
- 题目中某个值的总数量一定：比如图论中所有点的度数之和为 \(m\)，或字符串长度为 \(n\)；
- 数据范围长得比较奇怪，比如 \(10^{10}\)，既不像是筛法，又不像是什么数位 DP。
求解方法
因此，一般来说，根号分治的题目可以分为预处理阶段和枚举阶段：
- 预处理阶段：通过不同的算法将分成的两块分别计算；
- 枚举阶段：将两部分合并为一个结果，通常会用到数学知识。
具体步骤：
- 找到两种暴力算法，复杂度分别为 \(O(b)\) 和 \(O(n / b)\)；
- 根据 \(n\) 的大小选取算法，则复杂度为：\(O(\min\{b, n / b\})\)；
- 根据基本不等式，\(\min\{b, n / b\} \le n\)；
- 取分界点 \(B = \sqrt n\)，对分界点左、有分别选择较优的算法，复杂度降为 \(O(\sqrt n)\)。
应用
例题
题目：P3396 哈希冲突
题意：给定长为 \(n\) 的序列 \(\mathrm{value}\)，和 \(m\) 个操作：
A x y：询问 \(\sum\mathrm{value}_i\space[i \bmod x = y]\)；C x y：修改 \(\mathrm{value}_x = y\)。
点击查看题解
考虑两种暴力解法：
- 预处理 模 \(i\) 为 \(j\) 的下标，其中的元素之和；时间复杂度：\(O(n^2) + O(m)\)；
- 暴力求 每次询问都遍历 \(\mathrm ki + j \space (\mathrm k \in \mathbb Z^+)\)；时间复杂度：\(O(mn)\)。
考虑优化，即将两种算法合并：
- 模数 \(< \sqrt n\)：使用方法 \((1)\)，时间复杂度：\(O(n \sqrt n) + O(m)\)；
- 模数 \(> \sqrt n\)：使用方法 \((2)\)，时间复杂度：\(O(m \sqrt n)\)；
因此，优化后的总时间复杂度为 \(O((n + m) \sqrt n)\)。
练习题
见：https://www.luogu.com.cn/training/386103
Reference
[1] https://blog.csdn.net/qq_35684989/article/details/127190872
[2] https://www.cnblogs.com/weixin2024/p/17032201.html
[3] https://www.luogu.com.cn/blog/Amateur-threshold/pu-li-mei-xue-qian-tan-gen-hao-fen-zhi
[4] https://zhuanlan.zhihu.com/p/594018645
[5] https://www.luogu.com.cn/blog/340940/gen-hao-fen-zhi-xue-xi-bi-ji
[6] https://www.cnblogs.com/ray52033/p/15011464.html
[7] https://www.luogu.com.cn/blog/blue/solution-p3396