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

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

根号分治与其说是一个算法,更不如说是一种思想(trick)。

定义

根号分治,是一种对数据进行点分治的分治方式,它的作用是优化暴力算法;类似于分块,但应用范围比分块更广。

具体来说,对于所进行的操作,按照某个点 \(B\) 划分,分为大于 \(B\) 及小于 \(B\) 两个部分,两部分使用不同的方式处理。(一般以根号为分界,即 \(B = \sqrt n\),因为这样复杂度最平衡)

简而言之,根号分治就是:对数据范围分块处理,将多个暴力算法“拼接在一起”,实现优化复杂度的作用。

算法思路

理论基础

具体思路如下:

  • 对于数据的种类少的部分,可以全部维护;
  • 对于另一部分,不方便维护的,可以暴力求解。

题目特征

  1. 能将原问题分为一个大问题(即前文说的 \(>\sqrt n\))和一个小问题(即前文说的 \(<\sqrt n\));
  2. 小问题的情况不多,可以维护所有可能的答案用离线算法求解;大问题可以用暴力求解;
  3. 题目中某个值的总数量一定:比如图论中所有点的度数之和为 \(m\),或字符串长度为 \(n\)
  4. 数据范围长得比较奇怪,比如 \(10^{10}\),既不像是筛法,又不像是什么数位 DP。

求解方法

因此,一般来说,根号分治的题目可以分为预处理阶段枚举阶段

  • 预处理阶段:通过不同的算法将分成的两块分别计算;
  • 枚举阶段:将两部分合并为一个结果,通常会用到数学知识。

具体步骤:

  1. 找到两种暴力算法,复杂度分别为 \(O(b)\)\(O(n / b)\)
  2. 根据 \(n\) 的大小选取算法,则复杂度为:\(O(\min\{b, n / b\})\)
  3. 根据基本不等式,\(\min\{b, n / b\} \le n\)
  4. 取分界点 \(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\)
点击查看题解

考虑两种暴力解法:

  1. 预处理 模 \(i\)\(j\) 的下标,其中的元素之和;时间复杂度:\(O(n^2) + O(m)\)
  2. 暴力求 每次询问都遍历 \(\mathrm ki + j \space (\mathrm k \in \mathbb Z^+)\);时间复杂度:\(O(mn)\)

考虑优化,即将两种算法合并:

  1. 模数 \(< \sqrt n\):使用方法 \((1)\),时间复杂度:\(O(n \sqrt n) + O(m)\)
  2. 模数 \(> \sqrt n\):使用方法 \((2)\),时间复杂度:\(O(m \sqrt n)\)

因此,优化后的总时间复杂度为 \(O((n + m) \sqrt n)\)。代码如下:

#include <bits/stdc++.h>

#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 <= 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

热门相关:落地一把98K   代孕母亲:危险的关系   楚氏赘婿   宠物小精灵之庭树   重生之嫡女祸妃