牛客周赛B题：用差分数组秒杀区间修改，告别暴力超时

牛客周赛127打完之后我第一反应是这道B题终于出了个正经的套路题。题目本身不长数据范围给得很直白解法也很固定但群里还是有不少人卡在超时上。其实这类题就是典型的一看就会、一写就废的区间操作题核心套路是差分数组。这篇我就以这场周赛的B题为引子把从暴力到差分的完整推导、代码实现、常见坑一次性讲清楚适合还在周赛二题三题徘徊的选手也适合准备校招笔试、想补基础算法的朋友。1. 先看懂这道题牛客周赛B题在考什么1.1 周赛难度分层与B题的定位牛客周赛的题目通常按ABCD四题排列难度逐级递增。A题基本是签到考的是语法和最简单的模拟B题则开始有算法味一般对应Codeforces难度900到1200左右的题目。这个分段很有意思它不会让你去写平衡树或者网络流但会考察你有没有刷够基础题、能不能一眼认出经典模型。说白了B题就是一道过滤器过滤掉完全没训练过算法思维的人。过了B题的人会有一个共同感觉这题不是不会是太熟了。区间修改、区间求和、差分、前缀和、双指针、二分答案这几种模型轮流出现在周赛B题里。如果你把最近十场牛客周赛的B题拉出来看一遍会发现至少有六七场都能用差分或者前缀和直接秒掉。所以与其说是考算法不如说是考套路敏感度。看到区间加操作、看到n和m都到1e5量级脑子里就该立刻蹦出差分数组这个名字。1.2 题干还原与边界条件梳理这场B题的题面我回忆一下大意是给定一个长度为n的整数数组a下标从1开始初始数组全为0。接下来有m次操作每次操作给定三个整数l、r、x表示把区间[l, r]内的所有元素都加上x。所有操作结束后要求输出整个数组的最终结果。数据范围是n、m最高到1e5x可能为负数绝对值可能到1e9。别小看这个下标从1开始、初始全0的设定。很多人在本地跑样例一切正常交上去就数组越界或者输出错位就是因为没有把边界条件想清楚。初始全0的好处是差分数组构造起来非常省事不需要先处理原数组如果初始值不为0那就得先把原数组的差分算出来。后面代码部分我会给出两种写法先记住结论初始全0就用增量差分初始有值就构造完整差分两种思路都要会。这个题还有一个隐藏信息x是可能为负数的。负数的出现意味着你在写代码时不能因为测试数据没有负数就掉以轻心凡是加法运算都要考虑是累加增量不是覆盖修改。很多人这里理解错以为每次操作是把区间设成x那整个思路就跑偏了。2. 直接模拟为什么会超时暴力解法的复杂度陷阱2.1 暴力解法的思路与隐藏陷阱拿到这个题最直觉的写法是双重循环外层遍历m次操作内层从l循环到r把每个位置加上x。代码写起来确实简单不到十行就能搞定。如果你只在本地跑小规模测试比如n10、m5这代码完全看不出问题答案也非常正确。问题出在数据范围。n和m上限都是1e5最坏情况下每次操作的区间长度也是1e5那么总操作次数就是1e5乘以1e5等于1e10。1e10是什么概念普通C代码一秒钟大概能执行3e8到1e9次简单运算1e10次操作意味着至少需要十秒以上评测机不可能给你这么长时间。牛客周赛的时限通常是一秒或两秒所以暴力写法百分之百超时。这是算法竞赛里最常见的陷阱正确性不等于可行性。你在分析任何解法之前第一件事永远是算复杂度而不是急着写代码。很多初学者栽跟头不是因为不会差分而是因为压根没算过暴力会被卡死。哪怕你把暴力优化一点比如遇到整段区间加直接跳过中间步骤也只适合特殊数据对上限数据依然无效。2.2 从复杂度看数据范围设计的用心为什么出题人非要把数据范围压到1e5不是故意为难人而是在暗示你标准解法的复杂度。如果n和m只有1000那O(nm)的暴力写法可能卡着时限能过一旦到1e5O(nm)直接爆炸必须降到O(nm)或者O((nm)log n)级别。这种数据范围设计其实是一种出题语言读得懂的人看到1e5就知道该用什么量级的算法。我把两种复杂度的差距用生活化的例子解释一下。暴力做法就像你给一条街的住户发传单每接到一个从第50家发到第100家的通知你就挨家挨户跑一遍。如果这样的通知有一万个每条街有一万米长你光走路就累死了。差分做法则是你在街道入口的公告栏上写一句话第50到第100家的门缝里每家塞一张传单最后你从头到尾走一遍顺便把之前所有通知都汇总执行。同样是发完所有传单前者可能跑一万次整条街后者只需要从头到尾走一次。所以当你看到区间加、区间减这类批量修改操作时第一反应不应该是循环修改每个位置而应该是能不能把修改动作记录下来最后统一算。这就是差分数组的核心思想下一节详细拆。3. 差分数组的核心原理把区间修改变成O(1)3.1 差分到底是什么一个能看懂的推导差分数组的定义非常朴素对于原数组a构造一个diff数组满足diff[i]等于a[i]减去a[i-1]这里规定a[0]等于0。换句话说diff记录的是原数组相邻元素之间的差值。比如原数组是[3, 5, 8, 2]那diff就是[3, 2, 3, -6]。你可能会问这有什么用处关键在逆运算原数组a是差分数组的前缀和。a[1]diff[1]a[2]diff[1]diff[2]a[i]等于从diff[1]加到diff[i]。这个性质就是整个差分算法的基石。我们不去直接维护原数组而是维护差值。注意第3个差值-6正好是8到2的变化量它和前面两个差值的组合能完整还原出原数组的走势。打个比方原数组是一段路的海拔高度差分数组就是每一段路的坡度。知道起点海拔和每个坡段的坡度你就能算出任意位置的海拔不是吗3.2 区间加操作的转化过程现在看区间加操作怎么映射到差分数组上。假设我们要把a[l]到a[r]这个区间内的所有数都加上x。从差分的角度看区间内部相邻两个数的差值其实不会变a[l]和a[l1]同时加x差值不变a[l1]和a[l2]同时加x差值也不变。只有两个位置会发生改变。第一个位置是l。a[l]加了x而a[l-1]没加所以diff[l]的值会增加x。第二个位置是r1。a[r]加了x而a[r1]没加所以diff[r1]的值会减少x。看清楚是r1不是r。这是整个算法最容易出错的地方代码里写着diff[r1] - x很多人写成diff[r] - x结果区间尾部的值错得离谱。用数学式子证明一遍更直观。diff[l] a[l] - a[l-1]更新后变为(a[l]x) - a[l-1]所以增加x。diff[r1] a[r1] - a[r]更新后变为a[r1] - (a[r]x)所以减少x。区间中间的diff值保持不变。这样一次原本需要遍历整个区间的操作就变成了两个O(1)的数组修改。完整的三步流程是第一步初始化diff数组为全0或者根据原数组构造初始差分第二步对每一次操作执行diff[l]加x、diff[r1]减x第三步从头到尾做一遍前缀和得到最终数组。整个算法复杂度是O(nm)空间复杂度O(n)。3.3 为什么这里不需要线段树有些读者可能已经想到了线段树或者树状数组这确实是区间修改的常见工具但这个题用它们属于杀鸡用牛刀。线段树的优势在于支持在线查询和动态修改也就是边修改边问答案而本题是所有操作结束后输出最终数组属于离线处理的场景。差分数组正好克制这种离线区间修改一次还原就能得到全部答案。再从性能上对比线段树每次区间修改和查询都是O(log n)总体复杂度O(m log n n log n)在有nm1e5的情况下大概需要做百万次级别操作其实也能过。但线段树代码量大、容易写错、常数也大而差分数组O(nm)线性复杂度代码量只有十几行何乐而不为这也提醒我们算法选型不是越复杂越好而是匹配场景。能用前缀和解决的绝不写树状数组能用差分的绝不碰线段树这是竞赛里节省时间的重要经验。还有一点差分数组思想在后续很多题目里都会变体出现比如扫描线算法处理矩形面积并、树上差分处理路径修改统计。现在把一维差分吃透是这笔投资最划算的地方。4. 完整代码实现与细节解读4.1 C参考实现与两种写法我直接把比赛时用的代码贴出来注释写得详细点方便大家对照理解。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; // diff多开一位因为操作可能用到 diff[r1]r最大为n vectorlong long diff(n 2, 0); for (int i 0; i m; i) { int l, r; long long x; cin l r x; diff[l] x; diff[r 1] - x; } long long cur 0; for (int i 1; i n; i) { cur diff[i]; cout cur (i n ? \n : ); } return 0; }这段代码默认原数组初始为0所以diff只需要存增量。最后一步cur从diff[1]累加开始边累加边输出其实就是做前缀和。cur代表的是当前位置的最终值不需要再额外存一个结果数组直接输出即可。如果原数组初始值不为0那就有两种处理方式。第一种是把a数组读进来先构造差分for (int i 1; i n; i) diff[i] a[i] - a[i-1]; 然后继续执行区间操作最后做前缀和得到的就是最终数组。第二种是把a数组存下来diff只存增量最后输出时把a[i]加上累积的cur。两种都可以我推荐第二种因为增量差分独立于原数组逻辑更清晰出错率更低。4.2 高频踩坑点边界、溢出、输入输出这个题虽然代码短坑位一点儿不少我按踩中频率从高到低列一下。第一diff数组长度必须开到n2不是n1。为什么因为r最大是n操作里会有diff[r1]即diff[n1]的赋值。如果你只开到n这一步就越界写入了。C的vector越界写不会报错但会悄悄污染内存让你的答案在随机位置多出莫名其妙的值。这种Bug最难查因为你本地小数据可能碰巧不越界一上大数据就错。第二所有涉及累加的变量要用long long。n是1e5每次操作x的绝对值能到1e9极端情况下同一个位置被多次修改累积结果轻松超过int的20亿上限。int炸掉之后会变成负值输出一片混乱。记住一个经验看到累加两个字超过1e9的修改量无脑开long long。第三输入输出加速。竞赛里n、m每次读入1e5量级如果再用cin而不关同步可能白白多花上百毫秒。虽然这个题不一定卡输入但养成习惯总是好的。ios::sync_with_stdio(false)和cin.tie(nullptr)两行代码写在一开始基本是标配。第四多组数据的情况。如果题目有多组测试数据每组都要把diff数组重新初始化为0。很多人在本地测单组数据全对交上去WA就是因为上一组数据残留的diff值污染了下一组。用vector的assign(n2, 0)或者每次重新定义vector都行。第五还是下标问题。如果题目说数组下标从0开始那区间[l, r]的操作对应diff[l] x和diff[r1] - x没问题但要注意r1可能等于n而输出时只循环到n-1。下标从0开始和从1开始只是偏移量不同核心思想完全一样别把自己绕晕。4.3 拓展二维差分与同类题套路把一维差分吃透之后我建议顺手看一眼二维差分。二维场景下的问题长这样给定一个n行m列的矩阵初始全0有q次操作每次把左上角(x1, y1)、右下角(x2, y2)的矩形区域内所有元素加x最后输出整个矩阵。这是牛客和力扣里都很常见的变体处理思路和一维完全对称。二维差分的操作公式是四个位置diff[x1][y1]加xdiff[x21][y1]减xdiff[x1][y21]减xdiff[x21][y21]加x。最后做两次前缀和先按行累加再按列累加或者反过来就还原出最终矩阵。为什么右下角要加回来因为前面两次减法把重叠区域多减了一次所以要补回去。你可以画一个2x2的小矩阵手推一遍马上就能理解。这个拓展不是让你马上熟练掌握而是帮你建立起差分是一族思想的观念。除了二维差分还有树上差分处理树上路径的增量统计还有整数区间上的扫描线本质也是差分思想的延伸。一维差分是所有变体的地基地基打得越扎实后面学这些进阶内容就越快。5. 实战复盘常见问题与周赛节奏建议5.1 常见Wrong Answer场景速查表我在群里边看大家报错边整理了一张速查表覆盖了这个题绝大多数WA的原因这里直接分享出来方便你对号入座。报错现象可能原因排查方法样例全过交上去WAdiff数组长度不够r1越界检查vector长度是否为n2大数据点超时还在用双重循环模拟改用差分复杂度降到O(nm)输出值非常大且出现负数int溢出把diff和cur都改成long long结果前一半对后一半错diff[r1]写成了diff[r]回到差值定义重新推导一次多组数据时结果错乱上一组diff值残留每组开始前重置diff输出格式错误行尾多了空格用(i n ? \n : )控制分隔符最后一行可能有人觉得不算算法问题但周赛里因为多一个空格被判Presentation Error或者WA的情况非常多而且有时评测机给的是WA而不是PE你根本不知道哪里错。输出格式这种细节也要当成代码规范来对待写完代码就把最后一行单独检查。另外我还想提一个主动调试技巧自己构造一组小数据手工走一遍差分操作再和程序输出对比。比如n5三次操作分别是[1,3]2、[2,5]-1、[3,4]4手算得到期望数组然后跑代码。这个过程能排查掉百分之八十的边界错误。千万别只会依赖题目的样例样例太弱了几乎每个题都能构造出样例覆盖不到的反例。5.2 B题的时间分配与模板化训练最后聊点周赛的做题节奏。我的习惯是开局先把四道题都扫一遍花三分钟判断每题的题型。看到B题是区间加、数据范围1e5大脑就要立刻锁定差分模板看到最大值最小或者最小值最大这类关键词立刻想二分答案看到括号匹配、栈模拟立刻想栈或者单调栈。这种条件反射不是天生的是靠刻意训练养成的。B题建议从读题到AC控制在十分钟以内。如果十分钟还没写出来说明套路不熟先跳过做后面的题等全部做完再回头补。周赛不是只做一题而是要在有限时间内拿到最多分数。B题卡住不跳后面C题可能连读题时间都没有得不偿失。我在127这场就因为B题思路顺畅给后面的C和D留出了充足的推演时间。还有一个非常有效的训练方法每场周赛结束后把ABC三题整理成自己的模板笔记。笔记里不是抄题解而是写下次看到什么关键词、回忆起什么套路、注意什么边界。比如这道题我笔记里写了一句话区间增量累加差分数组O(1)改两端最后前缀和还原long long n2。下次再遇到类似的区间修改题我不用重新推导直接照着笔记模板秒写。坚持十场周赛你会有种顿悟感B题的坑来来去去就这么几个。差分数组这种题属于典型的会者不难难者不会它考的不是智商而是有没有见过、有没有练过、有没有把套路内化成肌肉记忆。希望这篇复盘能把你的B题速度提上一个台阶下次周赛再遇到区间修改题直接闭眼写diff稳得一批。