先说下背景这是我自己信奥刷题打卡系列里的一道题编号到了第 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, rp, r2p, ...它不是连续区间。强行用线段树来维护等差序列和无论是建树还是查询都很难处理。你也可以考虑开很多个树状数组每个模数开一份但模数的可能取值有 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 到 BB 是我们选定的阈值通常取 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 150000B 取 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, rp, r2p, ... 累加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 的取值预处理次数单次大模数查询最坏特点10150 万15000查询太慢1001500 万1500查询偏慢3875800 万387平衡推荐10001.5 亿150预处理偏大有 TLE 风险从表格可以看出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 只预处理到 Br 的范围是 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 运行超时原因速查症状可能原因解决方法大样例 TLE查询写成从 1 到 n 逐个判断改成等差跳转枚举大样例 TLE阈值 B 设得过大或过小让 B 接近 sqrt(n)大样例 TLE使用cin/cout且未加速改用scanf/printf或关闭流同步运行错误 RE访问f[p][r]时r p查询前先判r p输出 0内存超限 MLEf 数组开成MAXN * MAXB甚至MAXN * MAXN第二维开MAXB即可答案错误 WA修改后没更新预处理表遍历 p 更新f[p][pos % p]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 表是如何被修改操作维护的再去写代码。想通了维护过程代码基本不会写错。