基本技巧——根号分治 学习笔记
根号分治与其说是一个算法,更不如说是一种思想(trick)。
定义
根号分治,是一种对数据进行点分治的分治方式,它的作用是优化暴力算法;类似于分块,但应用范围比分块更广。
具体来说,对于所进行的操作,按照某个点 (B) 划分,分为大于 (B) 及小于 (B) 两个部分,两部分使用不同的方式处理。(一般以根号为分界,即 (B = 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
:询问 (summathrm{value}_ispace[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))。
考虑优化,即将两种算法合并:
- 模数 (:使用方法 ((1)),时间复杂度:(O(n sqrt n) + O(m));
- 模数 (> sqrt n):使用方法 ((2)),时间复杂度:(O(m sqrt n));
因此,优化后的总时间复杂度为 (O((n + m) sqrt n))。代码如下:
#include
#define ur uread()
using namespace std;
unsigned uread() {
unsigned num = 0; char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) num = num * 10 + ch - '0', ch = getchar();
return num;
}
const int N = 1.5e5 + 10;
const int M = 390;
int arr[N];
int f[M][M];
signed main() {
int n = ur, m = ur; int b = sqrt(n);
for (int i = 1; i
练习题
见: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
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net