如果你接手过“频繁给数组的某个区间统一加一个数 K”这类需求应该能体会到那种别扭感——写起来很简单数据一大就跑不动。长度十万的数组搞几万次区间更新直接双重循环一跑就是几分钟起步再赶上线上接口超时一个下午就耗在性能较劲上。这时候差分数组就是那个能让你把“跑不动”变成“轻松跑完”的技巧。简单说差分数组是一个用 O(1) 时间完成区间更新、最后用 O(N) 时间还原真实数组的算法思路专治“区间反复改、最后统一查”这类场景。这篇文章我打算把差分数组的构建、推导、实战和常见坑一次说清楚新手照着就能写老手也能拿去当参考。1. 先搞清楚痛点区间更新为什么慢1.1 朴素写法的复杂度瓶颈假设现在有一个长度为 N 的数组初始全是 0。业务上有一批操作每个操作给定一个区间 [l, r] 和增量 K要求把数组下标 l 到 r 之间的每个元素全部加上 K。这是最经典的“区间更新”模板很多数据处理脚本、批量统计系统里都会出现。最直观的写法就是双重循环arr [0] * n for l, r, k in operations: for i in range(l, r 1): arr[i] k这段代码的复杂度怎么算一次区间操作要遍历区间的长度所以单次操作复杂度是 O(r - l 1)。如果区间平均长度是 Mm 次操作的总复杂度就到了 O(m * M)。极端情况下每次区间几乎覆盖整个数组m 次操作就是 O(m * n)。我印象比较深的一次模拟实验数组长度 1,000,000执行 5000 次区间加法每次区间长度平均 500,000这种数据量下朴素写法的总操作次数大概是 25 亿次。在普通机器上用 Python 跑基本是几十秒钟起步即便换 C几亿次循环也需要肉眼可见的等待。放到实际系统里这种性能根本无法接受。问题的核心在于区间更新会反复触碰区间里的每一个元素而真正发生变化的信息往往只集中在区间的两个边界处。换句话说大量算力被花在了“重复搬运相同增量”上。1.2 差分的直觉把“改值”变成“改边界”如果你学过微积分对“导数”和“积分”的关系应该不陌生位移的导数是速度速度的积分是位移。差分和前缀和也是一对互逆操作。差分拿到一个数组计算相邻两项之差得到差分数组。前缀和拿到一个数组从开头累加到当前位置得到前缀和数组。这两个操作互相还原。原数组经过差分得到差分数组差分数组做一次前缀和又变回原数组。那么问题来了在一个数组上做“区间加法”反映到差分数组上会发生什么举个例子。数组 [0, 0, 0, 0, 0, 0]我们要给下标 2 到 4 的部分统一加上 3。修改后变成 [0, 0, 3, 3, 3, 0]。观察它的差分数组修改前差分[0, 0, 0, 0, 0, 0]修改后差分[0, 0, 3, 0, 0, -3]发现没有区间内部的值虽然都变成了 3但差分数组里只有两个位置发生了变化左边界 l 处加上了 3右边界 r 1 处减去了 3。也就是说区间更新这个“看起来要改一整段”的操作在差分视角下只需要改两个位置就能表达完整语义。这就是差分数组最核心的直觉用“变化的边界”替代“区间内每一个点的修改”。1.3 什么时候适合用差分差分不是万能的它的优势集中在“多次区间更新 批量查询还原”的场景。什么时候用它我总结了三句话更新操作远多于查询操作或者查询可以放到最后统一做的时候差分是首选。如果需要在任意时刻立刻回答“当前数组某个位置的值是多少”差分需要额外配合前缀和重建效率没那么直接这时候更适合考虑树状数组或线段树。如果区间是固定大小、固定次数、数据规模在百万级别以上差分基本就是最优解因为常数极小代码也短。2. 差分数组的原理与数学推导2.1 差分数组怎么构建直接看定义。假设原始数组是 A下标从 1 开始长度 n。定义差分数组 D其中D[i] A[i] - A[i - 1]通常约定 A[0] 0。也就是说D[1] A[1] - 0 A[1]D[2] A[2] - A[1]依此类推。构建过程用代码表示就几行def build_diff(arr): n len(arr) diff [0] * (n 1) # 多开一个位置方便处理越界 diff[0] arr[0] for i in range(1, n): diff[i] arr[i] - arr[i - 1] return diff注意这里我把 diff 数组长度开成了 n 1原因后面讲区间更新时你会看到r 1 可能正好等于 n多一个位置省得判断越界。有了差分数组之后怎么还原原数组对差分数组求前缀和def restore_from_diff(diff, n): arr [0] * n cur 0 for i in range(n): cur diff[i] arr[i] cur return arr这里 cur 是累加变量每遍历一个位置把当前差分值累加上去就得到了原数组对应位置的值。2.2 区间加操作的推导过程现在开始关键推导。假设要给原数组 A 的下标 l 到 r 区间内的每个元素加上 K我们只修改差分数组 D[l] 和 D[r 1]D[l] K D[r 1] - K然后对新的差分数组求前缀和得到数组 B。我们来验证这组操作的正确性。回顾前缀和的定义B[x] D[1] D[2] ... D[x]分三种情况看当 x l 时D[l] 的增量 K 还没被累加到 B[x] 中所以 B[x] A[x]不受影响。当 l ≤ x ≤ r 时前缀和的累加过程中已经包括了 D[l] 增加的 K但还没包括 D[r 1] 减少的 K因此 B[x] A[x] K正好实现了区间内统一加 K。当 x ≥ r 1 时前缀和既累加了 D[l] 的 K也累加了 D[r 1] 的 -K两者抵消所以 B[x] A[x]。这个推导过程建议自己拿笔在纸上写一遍。很多读者第一次接触时容易把“前缀和”和“差分数组当前值”搞混。差分数组的第 i 位只代表“这个位置相对前一个位置的变化量”它本身不是原数组的值只有做完前缀和之后才还原出真实数组。从复杂度角度看一次区间更新从 O(区间长度) 降到了 O(1)这是一个巨大的飞跃。n 次操作之后最后只需要做一次长度为 n 的前缀和还原整体复杂度 O(m n)m 是操作次数。2.3 三种实现方式复杂度对比实现方式单次区间更新m 次操作总复杂度查询/还原优点缺点朴素双重循环O(len)O(m * len)O(1) 直接读实现简单大区间多次更新直接超时差分数组O(1)O(m n)需要 O(n) 前缀和还原常数极小代码极短无法快速实时单点查询树状数组/线段树O(log n)O(m * log n)O(log n) 实时查询支持动态混合操作代码复杂常数较大从表里能直观看到差分牺牲了“实时单点查询”的能力换来了区间更新的极致速度。这是典型的“用空间的灵活性换时间”的思路。3. 实操案例从朴素版本到差分优化3.1 场景定义用我最近处理过的一个模拟项目来说。某跨平台系统的操作日志模块需要统计一段时间内每个时刻同时在线的事件数量。抽象成算法问题是这样的给定一个长度 n 1,000,000 的时间轴数组初始值为 0。业务产生 m 500,000 次事件每个事件有一个起始时间和结束时间对应区间 [l, r]以及一个增量 K比如新接入的连接数。要求最终输出每个时刻的总值。这个场景是差分数组最典型的使用方式大量区间更新最后统一输出。如果为了模拟真实感可以认为是某个预约统计模块在统计分时段流量本质上就是区间加法问题。我会用两版代码来对比。3.2 朴素实现的性能瓶颈先写出朴素版本import time n 1_000_000 m 500_000 # 构造一些测试数据这里简化为固定区间 operations [] for i in range(m): l (i * 37) % n r l (i % 1000) if r n: r n - 1 k 1 operations.append((l, r, k)) arr [0] * n start time.time() for l, r, k in operations: for i in range(l, r 1): arr[i] k print(朴素耗时:, time.time() - start)这段代码的问题就是 1.1 里分析的 O(m * len) 复杂度。在我本机真实测试中n 100,000、m 10,000 时已经需要好几秒n 1,000,000、m 500,000 时我没等它跑完因为预估操作次数在千亿级别磁盘都要跟着遭殃。这里的教训是双重循环在写业务逻辑时看着很自然但数据量一大瓶颈立刻暴露。上线前必须评估数据规模不能等接口超时了再去想优化方案。3.3 差分数组版本同样的任务用差分数组写import time n 1_000_000 m 500_000 operations [] for i in range(m): l (i * 37) % n r l (i % 1000) if r n: r n - 1 k 1 operations.append((l, r, k)) # 差分数组长度 n 1预留 r1 越界位置 diff [0] * (n 1) start time.time() for l, r, k in operations: diff[l] k diff[r 1] - k print(更新耗时:, time.time() - start) # 最后统一还原 arr [0] * n cur 0 for i in range(n): cur diff[i] arr[i] cur print(更新还原总耗时:, time.time() - start)在这个规模下差分版本的耗时通常在零点几秒级别和朴素版本相比是几个数量级的差距。核心原因就是每个事件只做了常数次操作500,000 次事件始终保持线性增长而不是成倍叠加。3.4 实测心得和小规模验证如果你在实际测试中想验证正确性可以先写一个 n 10、m 3 的小样例跑一遍朴素版本和差分版本对比输出是否一致。我一般会写个简单的断言def brute(operations, n): arr [0] * n for l, r, k in operations: for i in range(l, r 1): arr[i] k return arr def diff_solve(operations, n): diff [0] * (n 1) for l, r, k in operations: diff[l] k diff[r 1] - k arr [0] * n cur 0 for i in range(n): cur diff[i] arr[i] cur return arr ops [(1, 4, 2), (3, 6, 1), (0, 2, 5)] assert brute(ops, 7) diff_solve(ops, 7)断言通过之后再上大数据量能省下大量排查时间。这是我自己一直坚持的习惯小数据验证逻辑大数据验证性能。4. 实现中的典型坑与排查技巧4.1 边界条件r 1 越界问题差分数组操作里D[r 1] - K 是必须写在更新里的。当 r n - 1 时r 1 n已经超出原数组的有效下标范围。这也是为什么构建差分数组时要把长度开成 n 1。如果你只开了 n 长度这里就会数组越界轻则结果错误重则直接崩溃。我见过不止一个新人在这一步翻车把差分数组长度开成 n然后每次更新前先用 if 判断 r 1 n 再处理。逻辑上没错但多了一个分支判断而且容易漏掉条件导致错误。更稳妥的做法是长度直接开 n 1还原时只遍历前 n 个位置D[n] 的值自然丢弃。4.2 忘了做前缀和还原这是第二个高频问题。差分数组本身是“变化量”不是结果。如果在中途直接读取 diff[i] 当作原数组的值来用大概率得到的是各种增量叠加而不是真实值。比如前面那个例子差分更新结束后 diff 数组可能是 [5, 2, -3, ...]这和真实数组完全是两回事。我必须强调差分数组只是中间表示必须经过前缀和累加才能还原成业务需要的数据。这个操作千万不能省。一个更隐蔽的变体是如果初始数组不是全 0而是在一个已有值的基础上做区间更新那么你不仅要记录所有区间操作的增量还需要先把初始数组转换成差分形式再把操作叠加进去。具体来说先用初始数组构建 diff再执行 diff[l] K、diff[r 1] - K最后统一还原。很多人在“非零初始数组”场景下会直接漏掉初始差分导致最终结果整体偏差。4.3 正负号写反区间加法时左边界加 K、右边界加 -K。如果写反成 diff[l] - K、diff[r 1] K那么前缀和还原结果就是区间内统一减 K。最常见的表现是小规模测试数据结果和预期正好相反。排查方式很简单找一个小样例手动模拟一遍很快就会发现问题。我自己的排查经验是遇到“结果整体不对劲”但不报错时先手推一个 n 5 的小数组把 diff 的每一步变化写出来对照代码找差异。逻辑问题靠读代码经常发现不了靠手推一遍就非常直观。4.4 选型失误差分硬扛动态查询某个需求如果要求在每次区间更新后立刻查询数组某个位置的值差分数组并不擅长。你当然可以每次查询时重新做一次前缀和到目标位置但那样查询复杂度是 O(n)m 次查询就是 O(m * n)会瞬间爆炸。这种场景应该用树状数组维护差分数组区间更新仍然是 O(log n)单点查询也是 O(log n)代码也不复杂。简单说树状数组可以视作差分数组的动态增强版差分数组只适合离线批量处理的场景。我整理了一个选型速查表需求特征推荐方案多次区间更新最后统一输出差分数组多次区间更新偶尔单点查询树状数组维护差分区间更新 区间查询且实时性强线段树懒标记数据量小实现越简单越好朴素循环甚至都可以4.5 问题速查表症状可能原因解决办法结果比预期小很多漏掉了初始数组的差分构建先用原数组构建 diff再叠加区间操作结果整体错误或出现负数正负号写反检查 diff[l] K、diff[r 1] - K数组越界差分数组长度没开够长度开到 n 1中途取值结果不对把 diff 直接当原数组用了记住 diff 只是变化量必须做前缀和和朴素结果前半段一致、后半段不一致边界更新时 r 1 处理有误确认区间是闭区间 [l, r]r 1 是开边界5. 差分数组还能往哪些方向延伸5.1 批量区间统计的经典业务场景差分数组最直接的应用是“多次给预定区间加增量最后统计总量”。比如某会议室预约系统需要统计每天同时被占用的会议室数量每次预约对应一个时间区间和一个占用数量最后输出每个时刻的总占用。把时间轴看成数组每个预约就是一次区间加法差分数组一趟下来就出结果。这个模式很通用。再比如某些工具类系统里的“并发数统计”“访问量分时聚合”本质都是区间加法。很多业务里大家苦苦思考怎么用循环逐条累加其实换成差分视角代码量能减少一大截性能也完全不同。5.2 二维差分矩形区域更新差分数组不止能处理一维。在图像处理、矩阵统计、地图热力图等场景中经常要在矩形区域内统一加一个数。二维差分就是一维差分的高维扩展。假设矩阵 A二维差分矩阵 D区域更新公式如下以左上角 (x1, y1)右下角 (x2, y2) 为矩形统一加 KD[x1][y1] K D[x2 1][y1] - K D[x1][y2 1] - K D[x2 1][y2 1] K这个公式背后的原理是二维容斥在四个角上放置“变化标记”最后通过二维前缀和还原就能保证矩形内统一增加 K矩形外完全不受影响。二维差分的复杂度提升更明显朴素矩形更新是 O(矩形面积)二维差分把单次更新降到了 O(1)最后做一次 O(n * m) 的扫描还原。如果矩形区域很大、操作次数很多这个优化是数量级层面的。我在处理某个图像叠加透明图层之类的模拟项目时用过一次二维差分矩阵规模 2000 * 20005000 次矩形框选叠加朴素方法预估操作量接近百亿次而二维差分的总耗时几乎可以忽略不计。这个技巧非常值得收藏。5.3 树上差分树上路径更新如果数据结构再往上走一步就是树上差分。树形结构里对某个节点到祖先节点的路径做区间更新可以拆成节点的差分标记最后做一次 DFS 后序累加还原。常用于统计一棵树上多条路径的覆盖次数。虽然第一次接触会觉得绕但核心思路和一维差分一致都是把“区间内逐点更新”转化成“几个关键点的标记”。这里先不展开等后面我单独写一篇再聊。6. 写在最后的经验沉淀我自己用差分数组解决过不少实际问题从笔试题到业务脚本都碰到过。如果要总结一条最重要的经验那就是看到一个“区间更新”需求先问自己一个问题——最终是“所有更新完成后统一看结果”还是“每步更新后立刻要看某个位置”前者直接用差分后者先试试树状数组实在不行再上线段树。另外所有差分相关的代码我都建议保留一个“小样例对拍”的习惯。哪怕只是一个 10 长度的数组、5 条操作的随机样例跑一遍朴素版本和差分版本做对比也能拦截住 90% 的边界错误。这个方法听起来土但救了我很多次。最后分享一个小技巧如果原数组长度上百万、操作次数上百万Python 的纯 for 循环重建前缀和的耗时其实也不算极小。想再压一点时间可以用 itertools.accumulate 或者 numpy 的 cumsum 来做前缀和还原效果非常明显。核心算法不变只是把累加操作下沉到 C 层执行。差分数组的价值在于思路具体实现语言反而不太重要。