作为一个常年跟算法打交道的开发者我见过太多人被“区间更新”卡住明明前缀和能轻松搞定区间求和可一旦遇到“把[L, R]区间统一加上一个数”这种需求马上就开始写循环效率差不说代码还容易错。其实这类问题的解法早就有了它就是前缀和的“镜像”——差分数组。这篇内容不打算只贴公式我想把我自己用差分数组的完整思路、实现细节和踩过的坑都梳理一遍希望能帮你彻底玩转这个基础但极其好用的算法技巧。差分数组说白了就是前缀和的逆运算。如果你已经把前缀和当成区间求和的利器那差分就是专门处理区间更新的利器。它适合的场景非常明确大量操作都是对数组某一连续区间整体加上或减去同一个值而最终只需要查询若干次整体结果。学完这个技巧你再看这类题目基本上就是套模板的事。1. 先搞清楚差分与前缀和的“镜像”关系1.1 从一次差分操作看懂核心原理要理解差分数组我习惯用一个具体例子起步。假设你手上有一个数组a初始全是0a [0, 0, 0, 0, 0, 0]现在我要对下标2到4从1开始计数的话就是第3到第5个元素统一加上5。常见的笨办法是写个for循环从2遍历到4每个元素加5。但如果操作次数非常多比如有10万次操作每次区间长度又很大这种做法就会退化得非常厉害总复杂度是操作次数乘以平均区间长度很容易直接超时。差分数组的解法是先构造一个长度比原数组多一点的数组d初始也为0。对区间[L, R]做“加value”的操作只需要两步d[L] value d[R 1] - value真的是两步没有任何循环。以刚才的例子为例L2R4value5那么就是d[2] 5 d[5] - 5此时d数组变成d [0, 0, 5, 0, 0, -5, 0]接下来如果要对d做前缀和得到一个前缀和数组sum_d你就会发现一个神奇的现象sum_d [0, 0, 5, 5, 5, 0, 0]再把sum_d和原数组a逐位相加就得到了区间更新之后的结果a [0, 0, 5, 5, 5, 0, 0]正好是下标2到4被加了5其他位置不受影响。这就是差分的核心原理。你只需要想象一下差分数组记录的是“变化量在哪个地方开始在哪个地方结束”前缀和则把这些开始和结束累积成实际效果。1.2 为什么要叫前缀和的“镜像”前缀和是给定原数组预处理前缀和数组之后可以快速O(1)求出任意区间和。差分是给定原始数组构造差分数组之后可以快速O(1)完成任意区间加值。两者正好是互逆操作。我自己的理解方式是这样的前缀和把静态数列变成可快速查询的累积形式差分把动态修改变成可快速更新的累积形式。如果你把差分数组再做一次前缀和得到的就是原数组如果把原数组做一次差分得到的就是差分数组。这两条路完全对称。理解到这个层面你就不容易忘记差分的两条更新规则了因为它们是前缀和的逆过程的必然结果。这里还想多说一句差分数组操作的是“区间同时加一个值”的场景它并不适合那种每次区间加不同值的随机修改。如果每次操作是“把区间[L,R]改成某个数”或者“区间每个元素加不同的增量”差分就不够用了需要另想线段树之类的数据结构。所以第一步一定是判断题目类型别什么题都硬上差分。2. 差分数组的构建、更新与核心代码模板2.1 构建差分数组的常规方式差分数组的构建很简单对于长度为n的数组a我们定义差分数组d其中d[i] a[i] - a[i-1]i从1开始计数且a[0]视为0。这样得到的d有一个性质对d做前缀和就能还原a。但在实际做题时很少会真的先给你一个非全零的原始数组再用差分去修改。更常见的是初始数组a全为0然后进行若干次区间加值的操作。这种情况下甚至不需要显式初始化a只需要维护一个差分数组d。如果题目给了初始数组也可以用另一种方式构建先将d全初始化为0然后对每个位置i执行“区间[i, i]加a[i]”的操作也就是d[i] a[i]d[i1] - a[i]。这样构建和理解都统一到同一种更新规则里不容易写错。我给一个常见的模板代码用Python写的话思路极其清楚n 10 # 数组长度 d [0] * (n 2) # 多开两个位置防止越界 # 一次区间更新把[L, R]整体加x注意这里是闭区间 def range_add(L, R, x): d[L] x d[R 1] - x # 进行若干次区间更新 range_add(2, 4, 5) range_add(0, 3, 2) # 最后求前缀和得到更新后的数组 a [0] * n cur 0 for i in range(n): cur d[i] a[i] cur print(a)注意这个d数组多开了一个位置也就是d[R1]一定存在。如果你用C或Java推荐开一个大小为n2的数组因为R1最大会等于n下标0到n一共n1个位置再加一个冗余位置更稳妥。这个多开位置的细节看起来小实际非常关键否则边界判断会写得很痛苦。2.2 区间加、区间求和组合差分与前缀和配合很多刚学差分的人会问那我只想知道某个点最终的值怎么办上面这个模板已经回答了最后做一次前缀和遍历得到的就是每个点的最终值。如果题目只做区间更新最后查询一次整体结果那这个做法总复杂度是O(n m)其中m是区间操作次数。相比暴力的O(n*m)提升非常明显。还有一些进阶情况是既有区间更新又需要多次区间求和。例如先进行若干次区间加值接着来多个查询每个查询问[L, R]的区间和是多少。这时差分数组做完后可以得到最终数组a然后再对a做一次前缀和就能O(1)回答每个区间和查询。这种“差分做更新前缀和做查询”的组合非常经典。我自己遇到这种题目时脑子里会自动把处理流程固定下来用差分数组d记录所有区间加操作。对d做一次前缀和得到最终数组a。对a再做一次前缀和得到前缀和数组p。查询[L, R]区间和时直接返回p[R1] - p[L]。这里注意下标转换。如果你习惯0起始下标前缀和数组p里一般定义p[i]表示a[0]到a[i-1]的和那查询[L, R]就应该是p[R1] - p[L]。如果你习惯1起始下标那p[i]表示a[1]到a[i]的和查询[L, R]就是p[R] - p[L-1]。只要保持一致就好。我见过太多人代码写着写着突然把两种下标混在一起样例对了一提交就是数组越界或者答案错误。所以一定在写代码前先明确自己的下标约定。2.3 为什么区间更新时不用真的修改原数组这里还有一个值得展开的思维点。很多人看差分模板觉得太抽象我明明是想给a[2]到a[4]加5为什么只在d[2]加5、d[5]减5其实你在用差分时根本不直接操作a而是把“变化信息”暂存在d里。最后做前缀和的时候d[2]的5会顺着前缀和累积到a[2]、a[3]、a[4]身上而d[5]的-5会从a[5]开始把累积值抵消掉。于是中间那一段就像被“抬升”了一样。可以打个比方想象一个一排多米诺骨牌每个骨牌的高度表示数组的值。区间加5就相当于在第2块骨牌下面垫高5之后从第2块开始连锁传递一个“高度5”的效应直到第5块末端再放一个“高度-5”的抵消块让后续骨牌恢复原状。这样你不需要挨个调整每块骨牌只需要改变两个关键位置。这个思维模型帮我度过初学期也帮我向别人讲解时省了很多口舌。3. 从笔试到业务差分数组的真实应用场景3.1 经典算法题里的飞机预订与车辆预约差分数组最典型的应用之一是那种“有多个预约每个预约覆盖一段区间最后统计每个位置被覆盖多少次”的题。比如飞机票预订给定若干个预订记录每条记录是[start, end, seats]表示从start站到end站之间每站增加seats个乘客最后要求返回每个站的乘客数。这种题本质就是区间加完全可以用差分数组的模板直接做。更贴近日常工作的是车辆调度预约某出租车平台平台不断收到用户预约每个预约覆盖一个时间段需要统计每个时间段内同时运营的车辆数量。假设把一天分成若干时间片每个预约是一个区间加1的操作最后用差分数组统计每个时间片的车辆数复杂度极低代码也很短。如果你用暴力循环去处理每条预约预约多了之后单机跑起来都非常吃力。我建议拿到任何“区间覆盖次数”的题目都先想一想能否转成差分。判断标准很简单每个操作是否都等价于在某个连续区间内统一加一个常数如果是那差分几乎就是最优解如果每个操作的增量还随位置变化那才需要考虑更复杂的数据结构。3.2 二维差分把技巧从一维推广到二维标题里说的是区间更新但差分并不只是一维数组的专利。很多二维矩阵题目也经常用到二维差分比如在一个网格上画若干个矩形每个矩形内部的值统一加1最后要输出整个矩阵。这种问题如果暴力做矩阵大小和矩形数量一上来就非常难受。二维差分的思路是在一维差分的基础上对矩形的四个角进行修改。二维差分更新矩形的方法是假设矩形的左上角是(x1, y1)右下角是(x2, y2)要统一加value那么修改差分矩阵diff的四个位置diff[x1][y1] value diff[x21][y1] - value diff[x1][y21] - value diff[x21][y21] value最后对整个diff矩阵做二维前缀和得到的就是每个格子的最终值。这四个位置为什么这样改核心还是“起始和结束”的思想只不过现在两个维度都要考虑开始与结束于是就有左上角开始加、右上边界后减、下边界后减、右下角再补回去。如果你理解了“镜像”的含义二维差分其实是一维差分在另一个维度上的自然延伸并不难记。我第一次接触时硬背了这四个式子后来推导了一两次就再也忘不掉了。二维差分的关键坑点在于下标越界。矩阵是0下标的话x21或y21可能等于行数、列数所以差分矩阵要比原矩阵多开一行一列。这个和一位数组多开位置如出一辙。我建议任何差分实现都把数组开大一点点多一行一列的费用微乎其微但能避免一大堆边界分支。3.3 数据流场景中的批量离线路由统计除了算法题差分数组在实际数据开发中也有应用。比如公司日志系统里每天有大量事件每个事件有开始时间和结束时间你希望统计每个小时内同时活跃的事件数量。离线处理时按小时整除划分成时间片每个事件对应一个区间加1最终用差分统计每个时间片的活跃数。处理几十万条事件只需遍历一遍差分数组非常快。这里有个细节在处理大数据时时间片数量可能特别大比如精确到秒或者毫秒。这时差分数组长度可能无法直接开到很大那就需要做离散化把所有区间端点和查询点收集起来排序去重后只在这些点上做差分统计。离散化听着高级本质就是“只在变化发生的坐标处记录变化”。这个思路和差分的本质完全一致是差分从固定数组走向动态区间统计的关键一步。如果你理解到这一层再看很多竞赛题里的扫描线算法会发现里面也透着差分的影子。4. 实操中的常见问题与调试技巧4.1 边界条件犯迷糊R1到底要不要处理我自己刚用差分时出过错而且错得很典型题目说对[L, R]区间加值我每次都把L和R搞混或者忘记处理R1的位置。忘记处理R1的后果是区间右边之后的元素也会被错误地加上值而且越往后错得越离谱因为前缀和累积会一直延续下去。这里给一个我自己的检查方法写一个超小例子手动算一遍。比如数组长度是5区间[1,3]加7。预期结果应该是第1、2、3个位置加7第0和第4个位置不变。如果你只做了d[1] 7没有在d[4] - 7最后求完前缀和每个位置都会是7显而易见就错了。所以调试时先测一次只有单个区间更新的极端小样例能快速暴露边界逻辑问题。还有一个更隐蔽的边界问题是如果R已经等于数组最后一个下标那R1就超出原数组范围了。这也是我前面反复说差分数组要开n2的原因。如果你在更新前判断R1 n才执行减操作逻辑上也没错但判断分支一多就容易出问题。我更推荐直接把差分数组开大然后无脑执行d[R1] - value因为那个多余的位置只是用来“接住”抵消值不会参与最终结果。4.2 差分数组初始化时容易踩的坑有些题目给定的原数组不是全零比如一开始班里有50个人其中某些座位已经有人坐过的次数不同然后你要继续做区间加。这时候就需要把初始值也“塞进”差分数组。两种做法一种是直接用差分定义d[i] a[i] - a[i-1]构造另一种是把每个位置i当作区间[i,i]执行加a[i]的区间更新操作。我有时会看到同学用第二种方法图省事在循环里对每个i调用range_add(i, i, a[i])结果写完代码发现很慢因为这样是O(n)构建其实本身没问题只要别不小心把构建过程也写成内层循环。另一种常见坑是不想单独建数组a直接在读入时把值加到d里结果忽略了d[i1]要减去同样的值导致前缀和恢复后每个位置的值不断叠加。我自己写代码时偏好先把d全置0再一次性通过循环里两个操作用差分语义构建这样逻辑统一不容易漏。再补充一个心得如果你用的是Python注意数组长度大的时候直接用列表推导式创建大数组是正常的但如果循环有大量累加操作普通Python循环可能还是不够快。差分本身是O(nm)但Python里10万长度、10万次操作还是能跑的如果数据量上到百万级建议考虑用数组模块或者直接换C写。这不是差分的问题而是语言执行效率的问题提前了解能少走弯路。4.3 差分前缀和组合题目的自查清单我把自己做题时常用的一串检查项整理成清单每次提交前过一遍下标是0起始还是1起始整个代码是否统一差分数组是否多开了一两个位置区间更新是否在R1处做了减操作最终求前缀和时遍历范围是否覆盖原数组全部位置如果有多次查询查询区间转换是否正确题目是全部操作后一次性查询还是边操作边查询如果是后者单独用差分可能并不合适因为边操作边查询需要能快速获取当前状态这时候可能要配合线段树或树状数组。边更新边查询这个问题值得展开一点。差分数组适合的是“先进行一堆更新然后统一查询最终状态”的离线场景。如果操作和查询交替出现比如更新一个区间后立刻查一次某个区间的和那么你不能只靠差分因为每次查询前都需要重新对差分数组做一次前缀和复杂度又上来了。这种情况更适合用树状数组做区间加区间求和或者用带懒惰标记的线段树。别看差分简单选错场景一样会翻车。4.4 从笔试到工程题差分数组的调试经验实际笔试场景里差分数组最怕的不是逻辑错误而是隐形越界。很多语言里数组越界并不一定崩溃而是悄悄修改了相邻内存导致最终结果莫名其妙。排查这种问题时我一般会在差分数组下标更新那一行打日志打印L、R、value以及更新后d[L]、d[R1]的值确认数据是否符合预期。对于小样例还可以写一个暴力循环做对照随机生成多次区间操作后比较差分结果和暴力结果。这种对拍方式效率极高能帮我在几分钟内定位到边界错误。额外说一个工程题里的技巧如果数据规模很大差分数值可能会超出int范围。比如你做了上百万次区间加每次加10万那累积值很容易超过32位整数上限。用Python天然是任意精度所以无所谓但用C/Java的时候一定要记得用long long。这个坑我在真实项目中踩过一次当时统计某个业务指标短整型溢出导致数据异常排查了很久才发现是数据类型容量不够。从现在开始凡涉及区间更新的累计值我默认就开64位整数能省不少心。5. 扩展思路其他能用到差分的隐藏场景5.1 扫描线思想里的差分应用前面提过离散化其实扫描线算法同样离不开差分思维。想象平面上有一堆矩形要计算被覆盖过的区域面积或周长。经典扫描线做法是维护一个“事件数组”在每个矩形的左边界加1右边界减1然后沿x轴扫描并维护当前y轴上的覆盖段。这个“左边界加1右边界减1”的本质就是差分在二维空间中的变体。只不过扫描线通常还会配合线段树来维护连续覆盖段的长度因为覆盖的几何形状对最后求面积有影响不能简单对所有网格点做前缀和。但理解这层联系是有价值的。当你看到一道几何题突然觉得无从下手时可以试着用离散化后的差分模型去套在哪些坐标点上有“事件发生”事件是增加还是减少覆盖是否可以在事件点上累积状态这种思考方式对竞赛选手来说尤其重要。5.2 时间序列中的累计变化统计业务系统里也常出现类似差分的模式。例如一个促销活动用户在某一天开始参与持续N天后结束。系统要统计每一天的活跃参与人数。最简单的方式是维护一个每天参与人数数组从开始日加1、结束次日减1然后做前缀和得到每天的真实人数。这个做法几乎不需要额外解释却非常高效。再比如在推荐系统里某类内容的上线时间和下线时间是已知的想要统计每天有多少内容在线同样可以用差分。每次内容上线是一个区间加1下线是另一个区间加1的结束。当你有千万级内容时暴力遍历每个内容每一天的在线状态是灾难而差分配合离散化可能只需要处理千万级事件点。实际业务中处理这种数据时用MapReduce或者SQL都能写出类似的“事件累积”逻辑核心还是开始和结束两个记录。这里我多说一句工程上有时不需要精确到每个时间点而是以天或小时为粒度。只要粒度确定差分数组的长度就是有限的完全可以在内存里跑。如果粒度太细导致数组过大那就按时间戳排序后做事件扫描。理解“用事件变化代替逐点枚举”这个思想比死记差分模板更能应对各种变形题。5.3 差分与树状数组结合解决动态区间更新如果你想更进一步差分数组还可以和树状数组结合得到一种支持“单点查询”的高效结构。具体做法是用树状数组维护差分数组d那么区间加的操作在差分数组上是两次单点更新刚好是树状数组的强项查询某个位置的值时用树状数组求前缀和即可。这样你就能在做区间更新的同时随时O(log n)查询某个点的当前值。如果还想支持区间和查询那就需要维护两个树状数组这就是所谓的“区间加、区间求和”的树状数组高级用法。原理是将区间和表示为关于差分数组的前缀和公式拆解后需要维护d[i]和d[i]*i两个序列的前缀和。很多同学觉得这个公式难记但其实它就是建立在一维差分基础上的代数推导。我建议熟练掌握差分后再去学树状数组的区间更新思维上会顺很多因为你已经知道所有区间更新的本质都是“两个单点修改”。6. 总结一下我常用的差分数组实践建议写到这里差分数组的核心已经被翻来覆去拆碎了。对我来说这个技巧最大的价值不是背模板而是建立一种“用事件起止描述区间影响”的思维方式。拿到题的第一步永远是识别场景是不是大量的区间统一修改且最终只需要整体结果或少量查询如果是差分会是你手里最锋利的一把刀。最后再分享一个我实际写代码时的习惯我会把差分数组的操作单独封装成一个类或函数而不是直接散写在业务逻辑里。比如一个RangeUpdate类内部维护差分数组对外暴露add(l, r, val)和build()两个方法。这样做的好处是当后续需要扩展成二维差分或者离散化版本时我可以只改类内部调用方完全不受影响。代码可读性也更高别人拿到我的代码不用从头读懂整个业务逻辑就知道在做什么。根据我个人经验差分数组就像反向思维的一个缩影。前缀和解决“频繁问、静态数据”的问题差分解决“频繁改、最后看”的问题。两者不是竞争关系而是同一枚硬币的两面。你真正掌握了其中一个再学另一个几乎不需要额外时间。如果你正在准备面试或竞赛强烈建议拿出两三道区间更新的题目亲手用差分解一遍再暴力对拍一遍感受一下复杂度从O(n*m)降到O(nm)的痛快。那种转变正是算法的魅力所在。