差分数组详解：从区间修改到前缀和的高效算法-北京尧图网络

派大星最近在啃算法题翻来覆去就一句话差分数组真是个又萌又猛的家伙。别看这名字唬人背后的数学连小学一年级都算得过来——被减数减减数等于差可一旦把它放到数组上它就能把一段区间里一堆重复的加法操作压缩成两三个单点标记最后像多米诺骨牌一样哗啦啦倒过去一次性结算出最终答案。这篇文章想把这个“从一道减法到一套连锁反应”的思路掰开揉碎讲清楚它是什么、为什么管用、代码怎么写、坑在哪里。无论你是刚接触算法的初学者还是刷题卡在区间操作上的选手又或者工作中偶尔要处理时间段统计这类需求只要把差分数组吃透很多看起来麻烦的批量修改问题瞬间就变成了“记两头、算全场”。1. 为什么需要差分数组从“暴力遍历”到“聪明记账”1.1 一个让人头秃的问题反复给区间加值假设你手上有一个长度为 n 的数组初始全是 0。接下来会来 q 次操作每次操作都给你三个数l、r、v意思是把下标从 l 到 r 的闭区间内所有元素都加上 v。等所有操作执行完你需要输出每个位置最终的值。这题听起来人畜无害。最直接的想法当然是暴力每次读到一个操作就写一个 for 循环从 l 跑到 r逐个把元素加上 v。问题来了如果数组长度 n 是 10^5操作次数 q 也是 10^5那总操作次数就是 n 乘 q等于 10^10。这个量级的循环在普通程序里少说要跑几十秒甚至几分钟这在算法竞赛、面试笔试里基本就是“死缓判决”。用生活里的例子来说暴力法就像你有一个几百米长的货架每来一个搬运工你都要陪着他从货架这头走到那头在他负责的连续一段里一张一张贴标签。来了几百个搬运工你就要来回走几百趟脚底都被磨出水泡。真正的问题是这些搬运工负责的区间经常重叠很多标签会被反复贴在同一件商品上而你想知道的只是最终每件商品上贴了几个标签。既然最终状态才是重点那中间过程有没有更聪明的记账方式有这就是差分数组的用武之地。1.2 记账方式的转变把“改一片”变成“改两点”差分数组的核心想法特别朴素我不去实时改那个长长的原数组而是开一个辅助的“记账本”。每一次区间操作只在记账本上改动两个位置区间起点记一个 v区间结束位置的下一个位置记一个 -v。等所有操作都记完了再从头到尾把记账本累计一遍就能还原出原数组的最终值。为什么可以这样要解释清楚得先回到标题里那句话“被减数-减数差”。差分数组这个名字其实就是“相邻两个数相减得到的差数组”。给定原数组 a差分数组 d 的定义就是 d[i] a[i] - a[i-1]再加上一个起点 d[0] a[0]。反过来如果已知差分数组 d想找回原数组 a只需要不停累加a[i] d[0] d[1] ... d[i]。换句话说差分数组跟前缀和是一对互逆操作求完差分再求前缀和就把原来的数组复原了如同一串数字先被拆成一个个差值再像积木一样拼回去。这一点特别关键因为区间修改在“差分世界”里会变得异常简单。你原本要在原数组上连续修改一大片动辄影响几十万个元素但在差分数组上一次区间修改只需要改两个单点。修改量从 O(区间长度) 降到了 O(1)而且完全不会改变最终还原后的结果。这个“延迟结算”的思路正是差分数组高性能的源头。1.3 “被减数-减数差”到底帮了什么忙聊到这儿可能有人会问那我不就是在原数组上做了“多次减法”吗这跟小学学的被减数减减数有什么区别区别在于角色转换。在小学里被减数和减数是具体的数算出的差也是具体的数而在算法里我们把整个数组看成“被减数序列”和“减数序列”的差值。相邻两个原数组元素相减得到的是两个位置之间的“变化量”。这些变化量有一个很有意思的性质如果我在 a[5] 这个位置加了 3会让 a[5] 和 a[4] 的差变大 3同时让 a[6] 和 a[5] 的差变小 3。也就是说一个点上的修改只会波及差分数组里的两个位置。这与区间修改形成反差原数组的区间操作波及一大片但换算成差分数组一大片变动的“源头”和“结尾”只对应两个标记。所以差分数组常常被拿来当作区间操作的“代理”把复杂问题转化成简单问题。说白了原数组上让人头疼的“区间批量加”在差分数组里就是两次单点记账仅此而已。2. 差分数组的核心原理从“相邻相减”到“多米诺骨牌”2.1 三分钟学会构造差分数组构造过程没什么技术含量。假设原数组 a [1, 3, 7, 2, 8]按下标 0 开始。我们定义差分数组 d长度和原数组一样实际操作中通常多开一位原因后文会说并令 d[0] a[0] 1。接下来d[1] a[1] - a[0] 3 - 1 2d[2] a[2] - a[1] 7 - 3 4d[3] a[3] - a[2] 2 - 7 -5d[4] a[4] - a[3] 8 - 2 6得到 d [1, 2, 4, -5, 6]。用 Python 写两行就够a [1, 3, 7, 2, 8] d [a[0]] [a[i] - a[i - 1] for i in range(1, len(a))]用 C 的话可以原地构造省一个数组for (int i n - 1; i 1; --i) { a[i] - a[i - 1]; }这个原地写法要注意遍历顺序必须从后往前否则前面的 a[i-1] 已经被改过了减出来的就不是原始相邻差。很多新手踩过这个坑我建议刚开始还是老老实实开一个 diff 数组逻辑更清晰。如果有原数组那就用相邻相减来构造如果原数组初始全 0那差分数组自然也是全 0连构造都省了。后面要讲的区间操作题绝大多数都是“初始全 0 若干次区间加”。所以大多数情况下你只需要一个初始化为 0 的 diff不需要额外构造。2.2 还原过程就是多米诺骨牌连锁反应还原原数组时我们维护一个累积变量 cur从 d[0] 开始每一步把当前的 d[i] 加进 cur并把这个 cur 作为还原后的 a[i]。这个过程跟“多米诺骨牌”如出一辙第一张骨牌 d[0] 倒下后它的能量传导给下一张每张骨牌倒下时既继承了前面所有骨牌积累的“力量”又把这份力量继续往后传递。放在公式里a[i] a[i-1] d[i]而 a[i-1] 本身又是由更前面的差值累积来的。于是只要起点 d[0] 动了一点后面整条链都会跟着动像骨牌连锁反应一样不停歇。对前缀和思想不熟的朋友可以把这个过程想象成水库放水差分数组里的每一项是各个闸门放出的水流量水流进来之后不会消失而是不断往下游累积。你问某个位置的水量就把上游所有闸门的流量统统加起来。这就是前缀和的本意。还原代码也很短cur 0 for i in range(len(d)): cur d[i] a[i] cur如果你要还原的目标数组长度小于 diff 的长度因为 diff 可能多开了一位遍历时要注意只循环到目标数组长度为止不要把多开的那一位也当成了原数组的值。2.3 区间修改为什么只需要改两个点现在来看最核心、也是最“魔法”的操作。假设我们想让原数组的闭区间 [l, r] 内所有元素都加上 v那么在差分数组上只需要做两件事d[l] vd[r1] - v如果 r1 没有超出边界为什么有用我们还原前缀和时会发现d[l] 加 v 之后从 l 开始后面每一个还原位置 a 的值都会比原来多 v而 d[r1] 减 v会从 r1 开始把前面多下来的 v 抵消掉。两个标记一叠加真正被 v 影响的区间就恰好是 [l, r]。如果 r 已经到达数组末尾那么第二句可以直接不做因为后面已经没有需要抵消的位置了。有一个很形象的比喻差分数组好比一条直溜溜的滑轨从 l 位置放下一块小石头它会沿着滑轨一路滚到终点途中把每一处都垫高 v我们要想让它只影响 [l, r]就在 r1 的位置竖起一道挡板减 v把多出来的高度全部没收。滚石头和竖挡板就是两个单点操作。理解了这张画面区间修改再也不会记错。派大星第一次听这个比喻的时候开心得跳起来说这就是“一块石头加一道墙”我觉得这个描述比任何公式都更接近本质。3. 实战区间加法问题从暴力到差分3.1 完整题目与数据范围直接上硬菜。有一个长度为 n 的数组初始全为 0。执行 q 次操作每次操作给定区间 [l, r] 和数值 v要求将区间内所有元素加上 v。所有操作完成后输出数组中每个位置的最终值。限制条件很典型n 10^5q 10^50 l r nv 可以是负数也可以是 0。这是区间操作题最经典的版本几乎每个算法入门者都会遇到。如果用暴力法时间复杂度 O(nq)最坏情况 10^10 次加法。如果用差分每次操作 O(1)最后还原一遍 O(n)总体 O(nq)。从 10^10 直接降到 2×10^5 左右的量级这种提升幅度在算法题里属于“断崖式碾压”。项目暴力法差分数组每次区间修改O(区间长度)O(1)q 次操作O(nq)O(q)最后还原不需要O(n)总复杂度O(nq)O(nq)3.2 从零手写差分求解用 Python 写一遍全流程n 10 q 3 ops [ (2, 5, 3), (1, 8, -2), (4, 9, 5), ] # diff 多开一位长度为 n1这样当 r n-1 时不会越界 diff [0] * (n 1) for l, r, v in ops: diff[l] v diff[r 1] - v # 前缀和还原 res [0] * n cur 0 for i in range(n): cur diff[i] res[i] cur print(res) # 输出: [0, -2, 1, 1, 6, 6, 3, 3, 3, 3]手动演算过程方便对答案初始 diff 全 0长度 11。操作 (2, 5, 3)diff[2] 3diff[6] - 3操作 (1, 8, -2)diff[1] -2diff[9] - (-2)也就是 diff[9] 2操作 (4, 9, 5)diff[4] 5diff[10] - 5这个位置在还原时不会读到相当于安全丢弃最终 diff [0, -2, 3, 0, 5, 0, -3, 0, 0, 2, -5]。前缀和还原i0cur0res[0]0i1cur-2res[1]-2i2cur1res[2]1i3cur1res[3]1i4cur6res[4]6i5cur6res[5]6i6cur3res[6]3i7cur3res[7]3i8cur3res[8]3i9cur5res[9]5这个结果跟暴力验证完全一致可以自己拿纸笔核一遍。再看一个 C 模板用的是 1-based 下标竞赛里很常见#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorlong long diff(n 2, 0); while (q--) { int l, r; long long v; cin l r v; // 下标从 1 开始闭区间 [l, r] diff[l] v; diff[r 1] - v; } vectorlong long a(n 1, 0); long long cur 0; for (int i 1; i n; i) { cur diff[i]; a[i] cur; cout a[i] (i n ? \n : ); } return 0; }注意这里 diff 的长度开成了 n2因为下标到 n1 也能存。用 long long 也是必须的因为多次累加之后中间值可能超过 int 范围竞赛里因此挂掉的人不在少数。3.3 逐行拆解代码逻辑这段我们把 Python 版本讲透因为很多人代码能默写出来但一换姿势就懵。diff 数组长度开成 n1这是我最想强调的细节。因为操作里会出现 r1当 r 恰好等于 n-1 时r1 等于 n超出原数组下标范围。多开一位之后减掉的这个 v 会被存在 diff[n] 里而最后还原时我们只遍历 0 到 n-1根本不会读到 diff[n]相当于这个标记被安全丢弃。如果不加这一位就得写成 if (r 1 n) diff[r1] - v; 多一次特判也更容易漏。所以我的习惯是不管原数组多长diff 一律多开一位区间操作闭着眼睛改最后按原长度还原。为什么不直接在原数组上操作因为我们把每次区间操作浓缩成两个点之后所有操作彼此之间不会互相干扰。它们的叠加自然体现在 diff 每个位置的累加上。最后只需要从头到尾扫描一遍O(n) 就能还原最终数组。这个过程很像考试时先在草稿纸上把所有条件列出来最后再统一整理到答题卡上——中途不需要反复涂改。还原时的 cur 变量其实就是“前缀和的累计值”。它每一轮都是先 cur diff[i]然后把 cur 写入结果。你甚至可以不用 res 数组直接在原 a 数组上覆盖进一步节省空间。不过在面试里写代码清晰比省那一点点内存重要得多所以我推荐保留 res。3.4 复杂度与性能对比用数字说话。假设 n 10^5q 10^5暴力法最坏有 10^10 次元素访问按每秒 10^8 到 10^9 次简单运算估算需要 10 秒以上在大多数限时 1 到 2 秒的评测系统里必然超时。差分法 q 次操作各自 O(1)总共 10^5最后还原一次 O(n)总共 10^5加起来大约 2×10^5 次操作毫秒级跑完。换个角度想暴力法是每次区间修改都要亲自把所有涉及的格子都改一遍哪怕这个区间跟之前的操作重叠了一万遍差分法是统一记账每次修改只改两个标记最后统一汇算。数据量越大区间越长差分的优势越明显。这也是为什么在很多算法题里看到“区间加操作最终一次性查询”这种组合差分数组基本就是标准答案。甚至可以说这类题如果不用差分多半会超时用了差分代码量还比暴力短。4. 差分数组的进阶应用不只用来做加法4.1 时间段重叠统计公交车上下车模型差分数组最舒服的应用场景之一就是统计多个区间的重叠程度。举一个我让派大星印象最深的例子某自习室开放 N 个时段有 M 位同学预约每位同学预约了 [开始时段, 结束时段]问哪个时段同时在馆人数最多以及最多是多少人。用暴力做法对于每位同学的预约把对应时段的人数都加一最后再找最大值。若时段数量 N 和预约数量 M 都很大照样超时。换成差分diff[开始] 1diff[结束1] - 1最后求前缀和每个位置的值就是该时段同时在馆人数取 max 即可。举个例子5 个时段3 个预约A 预约 [1, 3]B 预约 [2, 4]C 预约 [3, 5]差分标记如下Adiff[1] 1diff[4] - 1Bdiff[2] 1diff[5] - 1Cdiff[3] 1diff[6] - 1下标 6 超出直接丢弃前缀和还原后每个时段的人数依次是 1、2、3、2、1。最大重叠出现在时段 3同时有 3 人在馆。这个过程非常像公交车到站每到一站都有人上车(1)有人下车(-1)车上实时人数等于累计的上下车人数差。只要把所有站点的“上车/下车变化”记下来最后刷一遍就能知道每一站车上有多少人。酒店预订、会议室安排、商店客流预测全是这个模型。面试里遇到这类题差分数组就是那个“一眼看穿”的解法。4.2 多次区间覆盖的最终颜色状态统计另一个常见场景一面墙长 n初始无色有若干次操作每次给区间 [l, r] 染上某种颜色最终问你每种颜色的格子数量。这里的关键是“覆盖”后染的颜色会覆盖先染的。如果只求最终状态差分可以配合“倒序处理”来用。从最后一次操作往前看某个区间一旦被当前这次操作覆盖过那么更早的操作里同样位置就不应该再被统计。具体做法是维护一个“是否已经覆盖完成”的标记数组配合差分对尚未覆盖的格子做区间计数。这个技巧比普通的区间加法要绕一些但核心仍然是“记账统一还原”。不过要提醒一句如果操作是“区间赋值/覆盖”并且要输出最终每个位置的具体值光靠一维差分是不够的因为覆盖不具有加法性后一次赋值会把前一次完全冲掉。这种时候要么用倒序差分技巧要么直接上线段树。差分数组真正最顺手的还是“区间加 v”这种具有叠加性质的操作。这不算劝退只是想说清楚边界省得到时候发现差分不是万能钥匙。4.3 二维差分从一维骨牌到二维版图一维差分学会了二维差分其实就是一个简单的推广。假设有一个 n×m 的矩阵初始全 0有多次操作每次把左上角 (x1, y1) 到右下角 (x2, y2) 的子矩阵整体加 v最后求整个矩阵的最终值。二维差分的修改公式维护辅助矩阵 dd[x1][y1] vd[x21][y1] - vd[x1][y21] - vd[x21][y21] v还原时先对每一行求一遍列前缀和再对每一列求一遍行前缀和或者先列后行本质是二维前缀和就能得到最终矩阵。为什么是四个点一维区间对应“两个端点”二维矩阵对应“四个角”。想象把一维的骨牌铺到平面上起点放一个 v 会让右下整片区域都被抬高 v所以需要在上边界和左边界各放一个 -v 把两侧拦掉但拐角处被拦了两次还需要在右下角补一个 v 加回来。这就跟矩阵求和里的容斥公式一模一样。二维差分是很多竞赛题的常客比如“给棋盘的若干子矩形加值最后输出棋盘状态”。如果你能自己推一遍公式而不是死记四个点就会发现它和一维差分的“记账—还原”思想完全同源。建议先把一维练得滚瓜烂熟再写两遍二维模板基本就不会有问题了。5. 常见问题与排查技巧实录5.1 区间边界“差一”问题这是差分数组里最高频的 bug。原因很典型不同题目里下标有的是 0-based有的是 1-based操作给的区间有的是闭区间 [l, r]有的是左闭右开 [l, r)。每换一次就有人把 l 和 r 写错。举一个具体例子。0-based 下标下想把区间 [1, 4] 加 1正确写法是 diff[1] 1diff[5] - 1。如果手一抖写成 diff[4] - 1还原时位置 4 的值会先被加 1 又被减 1最终只影响了位置 1 到 3。边界差了一个位置结果就完全错了。我的排查方法很简单写完之后先手工构造一个小样例比如 n5手动算一遍再跑代码对比。更稳妥的是写一个“暴力对拍小脚本”随机生成长度不超过 10 的数组和若干操作暴力模拟一遍再用差分代码跑一遍结果不一致就输出错误用例。这个方法在算法学习期几乎百试百灵强烈推荐。5.2 还原出来的数字对不上先检查原数组的初始值如果题目给定的初始数组不是全 0那差分数组的初始构造就不是“全 0 起步”了而是要先通过原数组相邻项相减得到初始 diff。很多人直接把 diff 全初始化为 0然后只做了区间操作的标记最后的前缀和结果自然少了初始数组的值。解决办法有两种要么把原数组的差分算出来并放进 diff要么在最后还原时先把原数组初始值 a[i] 赋给结果再在结果基础上进行前缀和累加。最常见的竞赛题都初始化为 0所以这个坑容易漏。遇到输出结果整体偏移的情况第一反应就应该是“初始数组的值有没有进 diff”。5.3 多个操作叠加后还原结果怎么检查差分数组里的标记是累积的多个操作在同一位置可能相互抵消或叠加。想快速检查一个区间的最终变化量可以直接把 diff 在该区间求一次前缀和如果想检查的是某个位置的值就从头累加到该位置。如果怀疑某步操作写错了可以只用两个操作做实验一个区间的尾巴正好顶住另一个区间的头这时在纸上画图最直观。比如操作 A 是 [1, 3]操作 B 是 [4, 6]B 的起点正好是 A 的终点加 1。差分标记分别是 A: diff[1]v, diff[4]-vB: diff[4]w, diff[7]-w。你会发现 diff[4] 处既有 -v 又有 w这两个标记叠加是正常现象代表 A 的“拦截墙”和 B 的“起点”重合了。如果你改完代码发现中间某个位置的累加值变得很奇怪检查一下是不是把两个标记写混了。5.4 负数和零值操作要注意什么v 是负数完全没有问题区间加 -2 等价于把 diff[l] 减 2、diff[r1] 加 2v 是 0 更没问题做了等于没做。所以差分数组对任意整数 v 都通用不需要额外特判。唯一的顾虑是数值范围大量正负值叠加之后中间结果可能很大。比如 n10^5每个操作都加 10^9diff 累加时可能超过 32 位 int 的范围。因此在 C 里建议直接用 long long不要为了省内存用 int。Python 则完全不需要担心溢出这也是很多人喜欢用 Python 刷题的原因之一。5.5 什么时候不建议用差分数组差分数组不是万能的。如果问题是“在线询问”打一个区间加操作后立刻查询某个点的值或者查询某个区间的和这就不能只用差分数组了。因为差分数组擅长的是“最后统一还原”无法高效支持穿插修改与查询。这种场景需要树状数组或线段树。另外如果操作是“区间赋值/覆盖”而不是“区间加”差分也无法直接模拟覆盖效应需要配合倒序处理或直接上线段树。刷题时遇到区间操作先看三点操作类型是否可叠加、是否只需要最终答案、是否要求在线查询。三个条件都满足“最终一次性输出”差分数组基本就是最优解只要出现“随时查”就得引入更高级的数据结构。我自己在刷差分数组的过程中最大的收获不是背住 d[l] v、d[r1] - v 这个公式而是养成了画图的习惯。每次遇到区间操作我都会在草稿纸上画一条横轴标出区间起点和终点再画出差分标记的“正负脉冲”还原时把这些脉冲从左到右叠加起来。脑内的“多米诺骨牌”一旦建立起来后面学二维差分、树状数组都会因为同一种直觉而顺畅很多。最后分享一个小技巧凡是看到“区间加最后查询”这样的题型先别急着写线段树。把差分数组模板写好、写好 long long、写好 n1 的边界通常几分钟就能完成。等真正遇到需要动态查询的题再请出树状数组和线段树也不迟。派大星常说脑子里有一个差分的“记账本”比背十个模板都管用。这句话我越品越觉得是真理。

差分数组详解：从区间修改到前缀和的高效算法

相关推荐

哥斯拉Webshell攻防演练复盘：加密通信原理与检测排查

REA模型实战：从订单系统重构看事件驱动领域建模

职业经验建模：把岗位SOP转化为可执行AI Agent

更多资讯

知识工作插件化：构建可编程、可组合的智能工作流底座

SQL题目面试避坑指南：从读题拆解到查询优化全链路

知识工作插件：面向知识工作者的模块化增强协议

SchoolDB四表DDL全解析：数据库设计从字段选择到约束实践

订单表慢SQL优化实战：联合索引、覆盖索引与深分页方案

Python实战英雄联盟胜率预测：从数据清洗到SHAP模型解释

今日更新

微信云开发旅游小程序实战：LBS打卡+UGC社交全栈方案

金融AI代理平台核心拆解：从多代理协作到财报分析实战

基于大数据的智慧旅游推荐与可视化平台架构实践

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？