根号分治¶
前置知识¶
分块
目标¶
理解“根号平衡”的思想
What¶
《2014年信息学奥林匹克中国国家队候选队员论文集》
对于题目中的某两个约束，它们是相互制约的，并且这种制约是“乘积”关系——步长和项数，总有一个不能太大。我们针对两个情况分别设计算法，然后讲两种算法结合起来，就能获得一个完整的解决问题的算法。
Why¶
我们所学过的大多数数据结构都擅长处理“连续区间”的询问，而不擅长间隔的位置之间的询问。 令区间间隔为 d，对于 �≤� 的情况预存部分和，对于 �>� 的情况暴力扫描，就可以保证算法的时间复杂度为 �(��) 了 根号分治，就是在预处理与询问的复杂度之间寻找平衡的一个算法。通常以根号作为问题规模的分界线，规模小于根号的询问可以 �� 预处理， �(1) 求出，而对于回答规模为 ≥� 的询问时，此时暴力枚举只需要 ≤� ，那么整个题目就可以做到 �� 。根号平衡的思想非常重要，它是几乎所有根号算法的核心思想。
How¶
例题，哈希冲突 - 洛谷¶
题意：根据数组下标 k mod p 的结果，相同的放到一个hash池当中（注意不是 a[i] mod k）。 多次询问，mod p 的情况是，值为 x 这个池子内的所有数字之和
思路1¶
初始化n^2，修改操作O(n)，m次询问，整体是O(nm)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N], n, m;
int ans[N][N]; // ans[p][k]表示模p余k
void init() {
for (int i = 1; i <= n; i++)
for (int p = 1; p <= n; p++)
ans[p][i % p] += a[i];
}
int ask(int x, int y) {
return ans[x][y];
}
void change(int x, int y) {
for (int p = 1; p <= n; p++) {
ans[p][x % p] -= a[x];
ans[p][x % p] += y;
}
a[x] = y;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
init();
while (m--) {
char op;
int x, y;
cin >> op >> x >> y;
if (op == 'A') {
printf("%d\n", ask(x, y));
}
else change(x, y);
}
return 0;
思路2¶
我们可以对一个题想出两个暴力，各有各自的长处和短处。如果我们能对数据范围进行分块处理，或者两个暴力分别算之后拼接在一起，就用两个合在一起的暴力，实现了正解。通常这个分界点可以取到 � 。所以叫根号算法。通过根号算法，我们就能实现两种操作时间复杂度的均分了 。
- 对于模数 �≤� ，利于预处理， �(1) 给出答案
- 对于模数 �≥� ，直接暴力计算，此时跳跃次数不会超过�
#include <bits/stdc++.h>
using namespace std;
const int N = 150005, M = 400;
int a[N], n, m;
int ans[M][M]; // ans[p][k]表示模p余k
int B;
// O(n*sqrt(n))
void init() {
for (int i = 1; i <= n; i++)
for (int p = 1; p <= B; p++)
ans[p][i % p] += a[i];
}
int ask(int x, int y) {
return ans[x][y];
}
// O(sqrt(n))
void change(int x, int y) {
for (int p = 1; p <= B; p++) {
ans[p][x % p] -= a[x];
ans[p][x % p] += y;
}
a[x] = y;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
B = sqrt(n);
init();
while (m--) {
char op;
int x, y;
cin >> op >> x >> y;
if (op == 'A') {
if (x <= B) printf("%d\n", ask(x, y));
else {
// 直接暴力 O(sqrt(n))
int ret = 0;
for (int i = y; i <= n; i += x) ret += a[i];
printf("%d\n", ret);
}
}
else change(x, y);
}
return 0;
}
总结¶
大纲上，属于 NOI 级
