差分这玩意儿我最初实际体会到它的价值是在某次做模拟项目X的时候。当时有个模型要对一张巨大的网格做区域涂色统计一次操作就是给某个矩形区域里所有格子加同一个值操作次数还不少。一开始用最笨的双层循环小数据看不出问题数据一上量直接卡死。后来换成差分思路同样的功能几行代码搞定速度翻了不知道多少倍。从那以后只要遇到“区间批量修改”“区域批量更新”之类的需求我的第一反应就是差分而且一维和二维两个版本几乎都是成对出现。不少人会把“二维差分”顺手打成“二位差分”其实说的就是矩阵里的一块区域整体加同一个数这种场景。这篇文章就围绕一维差分和二维差分展开讲清楚它们能解决什么问题、代码怎么写、边界怎么处理以及实际刷题或做项目时最常见的坑。1. 先从“区间批量加数”这个经典问题说起1.1 暴力循环到底慢在哪给定一个长度为 n 的数组初始值全部为 0。现在有 m 次操作每次操作把区间 [l, r] 内所有元素加上某个数 v。操作结束之后希望你输出整个数组。最直觉的写法就是循环arr [0] * n for l, r, v in ops: for i in range(l, r 1): arr[i] v这段代码的复杂度是 O(m * n)。如果 n 和 m 都在 10^5 级别这个复杂度就是 10^10 次操作普通机器跑基本等于超时。就算数据范围再小一些性能瓶颈也非常明显。问题的关键点在于每一次操作其实只关心一个区间但循环遍历却把区间里每一个点都重新加了一遍。这就造成了大量重复劳动。如果能把“区间”当成一个整体来处理把每个点的加法延后到最后一刻统一算效率就会完全不同。1.2 差分数组的核心思想差分数组是这样一种结构它本身也是一个长度为 n 的数组但它的意义不在于直接记录每个位置的值而在于相邻两个位置之差。定义原始的数组为 a差分数组为 d那么d[i] a[i] - a[i - 1]反过来如果已知差分数组 d可以通过前缀和恢复出原数组a[i] d[1] d[2] ... d[i]这看起来像绕了一圈但它带来了一个非常重要的性质对原数组 a 的区间 [l, r] 统一加上 v等价于对差分数组只改两个位置——d[l] 加上 vd[r 1] 减去 v。原因非常简单。区间内的每个数都加了 v所以相邻位置之间的差值没有变只有左边界 l 处a[l] 比 a[l - 1] 的差值凭空多了 v只有右边界 r 1 处a[r 1] 比 a[r] 的差值凭空少了 v。其他地方全部不受影响。这意味着一次区间操作从 O(n) 降到了 O(1)。等所有操作都记录完最后再做一次前缀和一次性把整个数组的值算出来。总复杂度从 O(m * n) 变成了 O(n m)。1.3 生活化类比电梯按钮的计数方式理解差分可以想象成电梯楼层按钮的“报到”机制。如果某人在一楼按下按钮到了五楼又取消或者反着来真正需要停的楼层只有中间的几层。你不必让电梯每经过一层都判断“这个地方要不要停”只需要知道什么时候开始有任务、什么时候任务结束。差分数组也是这个逻辑。开始位置记录一个“有人在这里上来了”结束位置的下一格记录一个“有人在这里下去了”到最后一算自然就知道中间段被覆盖了多少次。另一个更贴近生活的场景是打卡记录一列公交车从始发站到尾站每个乘客上车和下车都有一个站点。差分数组记录的是每个站点“上车人数 - 下车人数”的差值最后只要累计一遍就能知道每一站车里有多少人。2. 一维差分从原理到代码实战2.1 差分数组的构造方法构造一维差分数组其实有两种常见方式。第一种方式是直接根据定义计算相邻差a [0] original_list # 下标从 1 开始 d [0] * (n 2) for i in range(1, n 1): d[i] a[i] - a[i - 1]第二种方式更常用初始时假设原数组全为 0然后每给一个区间 [l, r] 加 v就执行 d[l] v、d[r 1] - v。当所有操作都做完之后前缀和直接得到最终数组。这个过程不需要先把原数组构造出来再转差分而是把“原数组赋值”本身也看成一次区间更新。也就是说差分数组在大多数实战场景里不是靠公式预先构造的而是通过操作一点一点“喂”出来的。2.2 核心操作区间加法的代码模板一维差分的区间更新模板任何一个新手都应该直接背下来n, m map(int, input().split()) d [0] * (n 3) # 多开几个位置防止 r 1 越界 for _ in range(m): l, r, v map(int, input().split()) d[l] v d[r 1] - v # 最后前缀和还原原数组 result [0] * (n 1) for i in range(1, n 1): result[i] result[i - 1] d[i]这里需要注意数组下标从 1 开始便于处理前缀和的语义。d 的长度多开一些通常是 n 3 或 n 5。当 r 等于 n 时d[r 1] 会落在 n 1 这个位置这一步不能省略也不能因为越界就跳过。举例说明。初始数组全为 0操作1区间 [2, 5] 加 3操作2区间 [3, 7] 加 2操作3区间 [1, 6] 加 4。执行完所有区间更新后d[1] 4d[7] - 4d[2] 3d[6] - 3d[3] 5d[8] - 2d[4] 到 d[5] 无额外改动等等这里要逐步叠加用表格展示最终差分数组和还原后的数组会更直观位置累计差分值前缀和1442373512401250126-397-458-23最终原数组为 [4, 7, 12, 12, 12, 9, 5, 3]完全符合三次区间更新的叠加结果。2.3 一维差分常见的三个变形除了最标准的区间加同一个数一维差分还有几个非常常见的变形套路。差分加等差数列。如果操作不是“加同一个数”而是“加一个等差数列”比如区间 [l, r] 每个位置分别加上一个公差为 k 的等差数列那处理方式就稍微复杂一些。此时需要两个差分数组一个记录常数项的差值一个记录首项随位置变化的差值。数学上可以推导出对应的二次差分形式这类问题通常出现在稍微难一点的模拟题中。差分加条件判断。有些题目不会直接给你“区间加 v ”这种指令而是给出某种条件比如“每个位置的最终值等于覆盖它的区间数量”。这时候一次操作其实就是给区间加 1。本质还是同一套模型。差分求覆盖次数。这个思想在做涂色、区间调度问题时非常有用。比如有若干个会议给定开始时间和结束时间希望知道某个时刻场内有多少个会议同时进行。每次操作就是 [开始时间, 结束时间 - 1] 加 1做完之后前缀和就是每个时刻的并发会议数。这个技巧在线段树之外是性价比极高的做法。3. 二维差分从一行扩展到一整个矩形3.1 二维前缀和与差分的关系二维差分就是一维差分在矩阵上的推广。一维的时候差分数组的前缀和等于原数组二维的时候差分矩阵的二维前缀和等于原矩阵。先回顾二维前缀和的定义。设原矩阵为 a[i][j]前缀和矩阵为 s[i][j]那么s[i][j] a[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1]这个公式是二维前缀和的基础。它把左上角到 (i, j) 这个矩形区域的所有元素和求出来。那么二维差分矩阵 d[i][j] 就满足一个相反的关系d 的二维前缀和等于 a。也就是说a[i][j] d[i][j] 以及它左上方向所有 d 值的二维叠加。反过来从 a 构造 d 的公式是d[i][j] a[i][j] - a[i - 1][j] - a[i][j - 1] a[i - 1][j - 1]这个公式看起来很对称也很好记。它跟二维前缀和公式正好是正负号互换的关系。3.2 矩形区域加法的四个更新点一维区间加法只需要改两个点二维矩形区域加法需要改四个点。假设要把左上角 (x1, y1)、右下角 (x2, y2) 的矩形区域内所有元素加上 v那么需要执行d[x1][y1] v d[x2 1][y1] - v d[x1][y2 1] - v d[x2 1][y2 1] v这四个更新点的记忆口诀是起点加两边界减右下角加回来。为什么右下角要加回来因为二维前缀和在计算过程中左上角会累加两次减掉一次。如果不把右下角加回来就会导致这个矩形区域之外的某些区域被错误地减两次。用一个 3 行 3 列的简单例子说明。区域是左上角 (2, 2) 到右下角 (3, 3)加 1位置更新后值(2,2)1(3,2) (x213, y22)-1(2,3) (x12, y213)-1(3,3)1这样四个点覆盖之后矩阵所有位置做二维前缀和会发现只有 (2,2) 到 (3,3) 这一块的值加了 1其他位置不受影响。这就是二维差分的核心。3.3 二维差分的完整实战模板实际写代码的时候二维差分的完整流程是三个步骤# 第一步构造差分矩阵通常可以初始化为全 0 n, m map(int, input().split()) diff [[0] * (m 3) for _ in range(n 3)] # 第二步执行多次矩形区域加操作 q int(input()) for _ in range(q): x1, y1, x2, y2, v map(int, input().split()) diff[x1][y1] v diff[x2 1][y1] - v diff[x1][y2 1] - v diff[x2 1][y2 1] v # 第三步二维前缀和还原最终矩阵 a [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): a[i][j] diff[i][j] a[i - 1][j] a[i][j - 1] - a[i - 1][j - 1]注意这里的还原不是简单地求一次前缀和再带一次负号而是直接用二维前缀和公式把 diff 累加回 a。还有一种写法是在原矩阵上直接原地做不需要额外开 afor i in range(1, n 1): for j in range(1, m 1): diff[i][j] diff[i - 1][j] diff[i][j - 1] - diff[i - 1][j - 1]这种做法省空间但会破坏原来的 diff 值适合后续不需要再次用到差分数组的场景。大数据量下二维差分比每次矩形区域都暴力循环要快非常多。一个 1000 x 1000 的矩阵做 10^5 次矩形操作暴力可能要执行 10^11 次加法差分只需要 4 * 10^5 次更新点操作加一次矩阵前缀和 10^6 次操作整体性能差距是几个数量级。4. 差分真正的用武之地从题海到实战场景4.1 涂色问题与区域覆盖统计差分算法最经典的应用场景之一就是涂色问题。给定一个图板或者网格每次操作把一个区域全部涂成某种颜色最后要统计每种颜色各占了多大区域。如果直接用扫描线或线段树处理代码量会比较大。但如果是单纯统计覆盖次数不需要维护颜色种类差分数组一颗区域加一区域减一最后前缀和。这个思路在模拟某些图像处理Demo时也经常用到。比如给一张图片的多个矩形区域加权需要得到加权后的亮度分布图。把矩形区域操作变成四个差分点的更新然后对整张二维网格做一次前缀和就能快速得到最终的灰度矩阵。4.2 多次区间修改后的一次性查询差分适合的场景有一个共同特征修改次数多但查询次数非常少甚至只在最后做一次整体查询。典型场景是批量报名统计。某活动报名系统里每个人可以选一个时间段 [start, end] 参加系统要统计每个时间点有多少人在线。每个人报名就相当于给区间加一最终遍历一次前缀和就能得到每个时间点的报名人数分布。如果人数和时间段数量都很大这种做法效率最高。反之如果修改和查询交替出现修改完马上要查某一个点的值查询完又要继续修改那么差分就不适用了这种情况更应该考虑树状数组或者线段树。4.3 一维差分和二维差分怎么选很多刚接触差分的读者会问一个很实际的问题什么时候用一维什么时候用二维答案其实很直接数据是一维的还是二维的取决于模型本身。数组、队列、时间轴、序列这类一维结构就用一维差分。网格、图像矩阵、棋盘、地图等二维结构就用二维差分。还有一个判断诀窍看一次操作描述中涉及了几个维度的坐标。如果操作参数是 (l, r, v)就是一维如果是 (x1, y1, x2, y2, v)就是二维。这不仅是数据结构上的区分也决定了你数组要开到几维。4.4 与线段树的对比什么时候不用杀鸡用牛刀差分和线段树经常被拿来对比。线段树功能更强大支持区间修改、区间查询、动态维护多种信息但实现复杂度也高。差分只能做到“修改后最后再整体查询”不支持随时查任意区间的值。如果你的需求是“改完一次之后不需要实时查最后整体统计一次”那差分是首选实现简单、常数小、代码不易出错。如果需求是“边改边查”甚至要查某个区间的和、最大最小值差分就不够用了线段树或树状数组才是合适的工具。实际比赛中很多看起来复杂的区间问题其实都能先转化成“多次区间加 最后一次性前缀和”的形式。做这种转化需要一点经验但多练几次之后看到题目就能条件反射地思考这个操作是不是只对某个闭区间生效如果是差分就是最快答案。5. 常见问题与排查技巧实录5.1 数组越界和边界条件一维差分最常见的错误是忘记处理 r 1 这个位置。当 r 等于 n 时r 1 等于 n 1如果数组没有多开几个位置就直接越界。另一种情况是在某些语言里数组下标从 0 开始处理前缀和时需要额外小心很容易差一。二维差分更复杂一些x2 1 和 y2 1 都可能等于 n 1 或 m 1。所以二维差分数组一定要多开两行两列确保减法点落在合理范围内。常见的做法是开 (n 3) x (m 3) 大小的数组尽量避免边界判断。5.2 修改操作必须成对出现差分的核心是保证差分数组的累计变化量为零所以每个区间更新操作都必须在两个或四个位置记录正负变化。如果只记录开始位置的正号忘记结束位置对应的负号最终前缀和的结果就会导致某个区域一直增加得不到正确结果。排查这个问题的方法很简单把所有更新操作执行完把差分数组整个打印出来检查它的末位是否回到了 0。如果不为 0说明有区间更新没有配对成功某个边界条件写错了。5.3 下标从 0 开始还是从 1 开始很多初学者在这个问题上反复踩坑。我个人的建议是在算法题和模拟数据中尽量把下标转换为从 1 开始这样前缀和的公式最自然也不容易在边界上出错。如果题目给定的是从 0 开始的下标可以在读入时统一加 1。虽然多了一次转换但后续逻辑会清晰很多。二维情况同样如此x1 1、y1 1、x2 1、y2 1 之后再进入差分数组。5.4 从“二位”到底指什么标题里的“二位差分”其实大概率是“二维差分”的笔误。在一些搜索平台上这两个词会同时出现但前者并不构成独立的专业术语。所以如果读者在任何资料中看到“二位差分”不要被迷惑直接按照二维差分的知识体系去理解即可。5.5 调试用的对拍技巧我不建议一开始就死盯着代码看逻辑。更高效的做法是写一个单测用一个很小的矩阵比如 3 x 4手动计算结果用来对拍。然后把暴力解和差分解的输出做对比数据范围可以小一点比如 5 行 5 列、10 次操作这样一眼就能看出哪一步出了问题。我这次的模拟项目X调试过程中就是靠一组 4 个测试用例快速锁定了二维差分更新时右下角加回点的坐标写反问题。这种问题如果不通过对比单纯盯着代码看很难发现。5.6 一种实用的纸面推导法遇到复杂的区间更新组合我习惯先用纸画一个矩阵把每次更新涉及的变化点标出来。不需要画完整的矩阵只需要画差分矩阵的变化点然后手动做一遍前缀和看看是否符合预期。这个方法看起来原始但效率很高。它把抽象的公式变成了具体的图像很多坐标写错、符号写反的问题都能在动笔的这一分钟内暴露出来。与其反复调试不如在动手编码之前先用纸面推导一遍。6. 经验总结与扩展联想差分算法的核心价值在于“化整为零”。它把一系列区间操作压缩成少量边界点的变化最后通过一次前缀和统一还原。这个思想不仅适用于一维和二维数组还可以推广到更高维度只是更新点的数量会从两个变成四个、八个维度越高更新点越多但本质逻辑不变。我在实际使用中的体会是差分不是万能的但它是性价比极高的一把工具。遇到区间批量操作先不要急着上线段树先问问自己能否用差分解决。很多时候答案都是可以的尤其是在只需要最终结果的场景下。另外差分跟前缀和就像一对孪生兄弟。前缀和解决“快速求区间和”的问题差分解决“快速区间修改”的问题。两者结合起来就能覆盖很多常见的算法问题。在后续如果接触到树状数组还会发现差分数组经常被用作树状数组的底层结构用来支持单点查询和区间更新。可以说差分为更复杂的数据结构打下了非常关键的思维基础。最后再分享一个小技巧动手写代码之前先手动模拟一个两行两列或三行五列的小例子。真算一遍之后很多边界条件都不用背自然而然就写对了。
