基本技巧——根号分治学习笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了基本技巧——根号分治学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基本技巧——根号分治学习笔记

根号分治与其说是一个算法，更不如说是一种思想（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)\)。代码如下：

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 <= n; ++i) {
        arr[i] = ur;
        for (int j = 1; j < b; ++j) f[j][i % j] += arr[i];
    } while (m--) {
        char op[2]; scanf("%s", op);
        int x = ur, y = ur; if (op[0] == 'C') {
            for (int i = 1; i < b; ++i) f[i][x % i] += y - arr[x];
            arr[x] = y;
        } else if (x < b) {
            printf("%d\n", f[x][y]);
        } else {
            int sum = 0; for (int i = y; i <= n; i += x) {
                sum += arr[i];
            } printf("%d\n", sum);
        }
    }
    return 0;
}

练习题

见：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文章来源地址https://www.toymoban.com/news/detail-710517.html

到了这里，关于基本技巧——根号分治学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！