企业官网建设流程全解析

先说下背景，这是我自己信奥刷题打卡系列里的一道题，编号到了第 2725 题。今天写的是洛谷 P3396 哈希冲突，一道用 C++ 实现、核心考点为“根号分治”（也叫阈值分治）的经典题目。题目名字里带“哈希”，但它和真正的哈希表实现关系不大，本质上是在考一个很实用的平衡思想：把查询按模数大小分成两类，小模数预处理查表，大模数直接暴力枚举。这篇博客我会从题意拆解、算法推导、完整 C++ 实现，再到踩坑记录，把整道题讲透。适合正在刷数据结构的信奥选手，也适合想搞懂“根号分治究竟是怎么一回事”的算法学习者。

1. 题目解读与核心思路拆解

1.1 题目到底在问什么

题目会给一个长度为 n 的数组，下标从 1 开始。接下来有 m 次操作，操作只有两种：

• 查询操作：给出模数 p 和余数 r，求所有满足i % p == r的下标 i 对应的a[i]之和。
• 修改操作：把某个位置a[x]的值改成 y。

举个例子。假设 n = 5，数组是a[1]=1, a[2]=2, a[3]=3, a[4]=4, a[5]=5。查询A 2 1，也就是求所有i % 2 == 1的下标之和，满足条件的是 i = 1、3、5，答案是1 + 3 + 5 = 9。然后把a[3]改成 10，再查同样的条件，答案就变成1 + 10 + 5 = 16。

题目数据范围是 n、m 都可以到 150000。这个规模意味着，如果你写一个最朴素的暴力——每次查询都从 1 到 n 枚举一遍，那最坏就是 O(nm)，算下来是 2.25 亿次？不，是 2.25 亿？等等，150000 乘以 150000 是 225 亿次操作，严重超时。

所以这道题表面上问的是“哈希冲突”，实际上是在问你：能不能找到一个聪明的方法，把每次查询的代价从 O(n) 降下来。

1.2 为什么常规数据结构不好使

你可能会想，这题能不能用线段树或者树状数组做？单点修改好办，问题出在查询上。线段树的强项是连续区间的和，但这题查的是“下标对某个模数取余等于固定值”的元素之和，这些下标是等差序列，比如 i = r, r+p, r+2p, ...，它不是连续区间。强行用线段树来维护等差序列和，无论是建树还是查询都很难处理。

你也可以考虑开很多个树状数组，每个模数开一份，但模数的可能取值有 n 种，空间直接爆炸。莫队那种离线算法在这里也不合适，因为查询完全由模数和余数决定，没有天然的左右端点可以滑动。

所以常规套路在这里都不灵，需要换一个思路。

1.3 一个此消彼长的关键观察

根号分治的出发点是一个很朴素的观察：模数 p 小和模数 p 大，查询的难度是不一样。

• 如果 p 很大，比如 p > sqrt(n)，那么从 r 开始，每次加 p，在整个数组 1..n 范围内最多只有 n/p 个这样的下标。n/p 是小于 sqrt(n) 的，暴力枚举这些下标，一次查询的代价很小。
• 如果 p 很小，比如 p ≤ sqrt(n)，虽然 p 的取值不多，每种 p 的余数集合也不大，但我们可以提前把所有小 p 对应的“每个余数的元素和”都预处理出来，这样查询就是 O(1) 查表。

这就是根号分治最核心的思想：对于参数规模小的那部分，用预处理换时间；对于参数规模大的那部分，直接用暴力，因为暴力本身也快。两个方法互补，整体效率就上去了。

你可以把这个思想类比成“校内食堂打饭”：人少的窗口直接排队买，又快又简单；人多的窗口提前用 App 订好餐，到了直接取。两种策略分开用，都比“不管哪个窗口都死排”要强。

2. 根号分治算法设计

2.1 预处理 f 数组：把小模数查询变成查表

先定义一个二维数组f[p][r]，表示所有满足i % p == r的a[i]之和。这里的 p 取值是 1 到 B，B 是我们选定的阈值，通常取 sqrt(n) 附近。

预处理过程非常直白：

for (int p = 1; p <= B; p++) { for (int i = 1; i <= n; i++) { f[p][i % p] += a[i]; } }

这个两重循环的含义是：对于每个小模数 p，把所有元素按照“对 p 取模等于几”分成 p 个组，求出每个组的和，存到f[p][0]到f[p][p-1]里。

复杂度是 O(n * B)。当 n = 150000，B 取 388 左右时，预计算量大约是 5820 万次，在 C++ 里是很轻松的量级。

这里要注意，f数组的第二维不需要开成 n 那么大。因为对 p 取模的结果一定在 0 到 p-1 之间，而 p 最大就是 B，所以第二维开到 B 就够了。这一点我后面还会强调，因为它是很多人写挂的坑。

2.2 查询：小模数查表，大模数等差跳

有了预处理表之后，查询(p, r)分两种情况：

• 如果 p ≤ B，直接输出f[p][r]，一次查询 O(1)。
• 如果 p > B，直接枚举 i = r, r+p, r+2p, ... 累加a[i]，一次查询 O(n / p)，因为 p > B，所以不会超过 O(n / B)，也就是 O(sqrt(n)) 级别。

写成代码就是：

if (p <= B) { ans = f[p][r]; } else { ans = 0; for (int i = r; i <= n; i += p) ans += a[i]; }

这里有一个细节：当 r = 0 时，满足条件的下标是 p, 2p, 3p, ...，不是从 0 开始。虽然数组a[0]如果是全局变量默认为 0，加了也不影响答案，但严谨写法是判断一下，让循环从 p 开始。后面避坑部分我再详细说。

2.3 修改：把变化同步进 f 表

修改操作C x y要把a[x]改成 y。如果每次修改都重新跑一遍预处理，那复杂度就回到 O(nB) 了，肯定不行。正确做法是只更新受影响的表项。

设diff = y - a[x]，也就是变化量。更新a[x] = y之后，所有包含a[x]的f[p][r]都需要加上 diff。而a[x]究竟属于哪个余数组？很简单，就是x % p。所以：

int diff = y - a[x]; a[x] = y; for (int p = 1; p <= B; p++) { f[p][x % p] += diff; }

一次修改要遍历 1 到 B 的所有 p，复杂度 O(B)。你可能觉得 O(B) 也不小，但它和查询的 O(sqrt(n)) 是同一个量级，整体是均衡的。

注意 diff 可以是负数，因为新值可能比旧值小。f 表用 long long 存储，就是为了应对累加结果以及负数更新。

2.4 阈值 B 怎么选：复杂度推导

根号分治最核心的步骤其实是选阈值 B，选得好不好直接影响能不能 AC。

总的复杂度可以写成三部分：

• 预处理：O(nB)
• 每次修改：O(B)
• 每次查询：如果是小模数 O(1)，大模数 O(n/p)，上限是 O(n/B)

最坏情况下所有操作都是查询，那么总复杂度是O(nB + m * n/B)。如果 m 和 n 同数量级，B和n/B之间就是此消彼长的关系。当B = sqrt(n)时，两者相等，总代价最小。

我用一个表格来展示不同 B 对复杂度的影响，n = 150000 时：

从表格可以看出，B 太小会让查询退化，B 太大又会让预处理好一会儿。代码里一般这样取：

int B = min((int)sqrt(n) + 1, MAXB - 1);

这里sqrt(n) + 1是为了防止sqrt(n)取整后偏小，再加个保险。后面的MAXB - 1是为了防止 B 超过我们声明的数组边界，属于安全措施。

3. C++ 完整代码与逐段精讲

3.1 可直接 AC 的完整代码

下面这段代码是完整的可通过版本，用了scanf/printf，数组大小按 n = 150000 设计。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 150005; const int MAXB = 405; int n, m; int a[MAXN]; ll f[MAXB][MAXB]; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int B = min((int)sqrt(n) + 1, MAXB - 1); // 预处理 f[p][r]：所有 i % p == r 的 a[i] 之和 for (int p = 1; p <= B; p++) { for (int i = 1; i <= n; i++) { f[p][i % p] += a[i]; } } while (m--) { char op; int x, y; scanf(" %c %d %d", &op, &x, &y); if (op == 'A') { int p = x, r = y; // 余数必须小于模数，否则一定为 0 if (r >= p) { printf("0\n"); continue; } if (p <= B) { printf("%lld\n", f[p][r]); } else { ll ans = 0; // 余数为 0 时，从 p 开始枚举 for (int i = (r == 0 ? p : r); i <= n; i += p) { ans += a[i]; } printf("%lld\n", ans); } } else { int pos = x, newVal = y; int diff = newVal - a[pos]; if (diff == 0) continue; a[pos] = newVal; for (int p = 1; p <= B; p++) { f[p][pos % p] += diff; } } } return 0; }

3.2 代码里的几个关键决策

先看f数组的维度。很多人第一次写会开成f[MAXN][MAXN]，觉得余数最多到 n，所以第二维也要 n。这是错的：f[p][r]里的 p 只预处理到 B，r 的范围是 0 到 p-1，所以第二维最大也就是 B-1。开MAXB * MAXB完全够用，内存大约是 405 * 405 * 8 字节，1.3 MB 出头。如果按MAXN * MAXB来开，那就是 150000 * 405 * 8 ≈ 486 MB，直接内存爆炸。

再看查询分支。为什么先要判r >= p？因为i % p的结果永远落在[0, p-1]区间，如果余数 r 大于等于 p，那么任何下标都不可能满足条件，答案是 0。这个不判的话，小模数查询访问f[p][r]会越界，大模数查询从 r 开始枚举得到的也是错误结果。

修改分支里，diff可能是负数，所以要用int，不能只加正数。如果diff == 0，说明新值旧值一样，直接跳过。这个优化虽然不影响正确性，但能省掉一部分无谓的更新。

3.3 常数优化与内存说明

如果你跑这道题时发现时间卡得很紧，或者你想写一个更快的版本，可以把预处理里的% p运算优化掉。取模运算在 CPU 里是比较慢的，而这里每次循环都用到了它。一个替代写法是：

for (int p = 1; p <= B; p++) { int t = 0; for (int i = 1; i <= n; i++) { f[p][t] += a[i]; t++; if (t == p) t = 0; } }

这种写法用简单的加法和比较替代取模，实测下来能省不少时间。不过说实话，以 n = 150000 的数据量，即使不优化也基本能过，这个版本只是作为一个锦上添花的技巧记录下来。

输入输出方面，建议统一用scanf/printf。这道题 m 有 15 万，读写量不算大，但字符和整数混在一起，用cin不加ios::sync_with_stdio(false)的话容易拖慢速度。如果你习惯用cin/cout，记得在main开头加上：

ios::sync_with_stdio(false); cin.tie(nullptr);

并且读字符时用cin >> op，它会自动跳过换行和空格，不会像scanf那样需要手动写" %c"来吞空白。

4. 常见问题与避坑指南

4.1 余数大于等于模数：最容易翻车的边界

这道题我最早自己写的时候，就栽在r >= p这个边界上。当时觉得模数 p 和余数 r 都是输入给的，应该保证合法吧？结果用f[p][r]直接访问，程序直接数组越界，本地跑样例也没测到这种数据，提交上去不是 RE 就是 WA。

正确的姿势是：任何一条i % p == r的查询，先判断r >= p，如果成立，直接输出 0。这个判断看起来简单，但它的意义不只是防数组越界，更是在提醒你：输入数据里的余数是有可能大于等于模数的，题目没保证这一点。

4.2 余数为 0 时，枚举起点要小心

大模数查询时，如果余数 r 是 0，满足条件的下标是 p、2p、3p，也就是从 p 开始跳。如果写for (int i = 0; i <= n; i += p)，虽然全局数组a[0]恰好是 0，加上去没影响，但这种写法在两种情况下会出问题：

• 如果你把数组大小开成MAXN，并且某个角落的操作把a[0]的值改了，就会悄悄算错。
• 如果题目改成下标从 0 开始，那你的逻辑就全乱套了。

所以代码里我专门写了(r == 0 ? p : r)作为枚举起点。这类细节平时多留个心眼，比赛时就能少一次无意义的提交。

4.3 修改操作的两个参数含义别搞混

操作有两种，一种查询A p r，一种修改C x y。它们的第二个参数含义完全不同：查询里是模数，修改里是下标位置。

我第一次写的时候，为了方便，把查询和修改统一用x, y接收，然后在op == 'A'里把x当模数、y当余数，在else里把x当下标、y当新值。这本身没问题，但有一次脑子短路，在else分支里写成了f[x % p][...]，把修改位置当成了模数去更新。这种错误非常隐蔽，因为样例可能恰好碰巧能过，但大数据一定挂。

我的建议是：在代码里显式地命名，比如查询分支里叫mod和r，修改分支里叫pos和newVal，减少混淆的可能性。

4.4 运行超时原因速查

5. 从 P3396 看根号分治的更多玩法

5.1 离线优化：只预处理出现过的模数

如果这题改成 n 很大，比如 n = 1000000，但查询里出现的模数种类只有几十种，那 O(nB) 的预处理就可能扛不住。这时候可以离线处理：先把所有操作读进来存下来，收集所有查询操作里的模数 p，只对这些 p 预处理 f 表。修改操作也只更新有记录的 p。

这相当于把“泛化预处理”变成“按需预处理”，是一种很常见的优化思路。虽然原题用不上，但如果你在别的题目里看到类似的“查询模数种类少而 n 大”的情况，记得留这一手。

5.2 根号分治在其他题型里的影子

根号分治并不是只存在于这一道题里，它是一种非常通用的思想。我在刷题过程中遇到过好几类类似的场景。

一类是序列分块：把 n 个元素分成约 sqrt(n) 块，区间加、区间求和时，整块打懒标记，散块暴力。复杂度也是 O((n + m)sqrt(n))。这个思想在“分块入门”类型的题目里很常见。

另一类是图上度数分治：给定一张图，支持单点修改点权和查询某个点所有邻居的点权和。对度数很大的点，预处理一个“邻居和”数组；修改某个点时，更新所有大度数的点的邻居和；查询时，如果这个点度数大，直接查表，否则暴力枚举它的邻居。这样单次操作的复杂度也能控制在 sqrt(边数) 附近。

学会根号分治之后，你对“平衡”这两个字的理解会深很多。很多看似难搞的题，其实都是把操作按规模分成两类，各自用最合适的办法处理。

5.3 如果题目再变难一点呢

如果这题从单点修改变成区间修改，预处理表f[p][r]的同步就会变成区间问题，单靠一个二维数组就不够了。你可能需要给每个余数分组挂一个数据结构，比如树状数组，来支持区间加和点查询，复杂度会变成带 log 的版本。

如果查询模数 p 可能大于 n，或者余数 r 的范围可能超过 p，那边界处理会更复杂，但核心的“小模数查表、大模数暴力”思想仍然成立。建议你在把基础版写熟之后，自己尝试改改数据范围，再想想能怎么扩展。

最后分享一点个人心得

这道题我一开始也走过弯路，总想着找一种“统一的高端数据结构”一次性解决所有查询，结果越想越复杂。后来看到根号分治的解法，才意识到很多问题的解法其实不需要那么“高”，关键是想清楚什么情况下数据规模自然变小、什么情况下值得用空间换时间。打卡刷题刷到 2725 题，这种“分而治之”的直觉已经成了我拿到题目后的第一反应。最后给个小建议：做这种题目，一定要先手算一遍样例，体会 f 表是如何被修改操作维护的，再去写代码。想通了维护过程，代码基本不会写错。