1. 从一道卡的题目说起区间操作的暴力困境先讲个真实场景。前段时间某交流群里有人贴了一道题大意是有一个长度为 n 的数组初始全是 0现在有 m 次操作每次把区间 [l, r] 内的所有数统一加上一个值 c问所有操作结束后数组变成什么样。n 和 m 的规模都在十万级别。底下评论区清一色的回答是差分。提问的人一脸懵差分是什么为什么我看到这种题就只知道两重循环其实这种反应太正常了。遇到区间加这种描述第一反应是写循环去遍历区间里每个位置这是人脑最自然的想法。但你想过没有如果每次操作都遍历 [l, r]极端情况下每次都是全区间 [1, n]m 次操作就是 m × n 次赋值十万乘十万是 100 亿次运算在绝大多数评测环境里直接给你跑出五分钟都跑不完的体验。那有没有办法让区间加这个动作本身变快差分就是干这个的。在我拆开讲之前你先记住一句话差分解决的核心问题是把对一整段区间做修改压缩成只修改区间的两个端点。至于为什么能这样压缩后面我会用买菜找零钱的例子给你讲透。这篇文章我不会堆术语而是从本质逻辑出发把差分的原理、数组构建、题型识别、易错边界全部过一遍。不管你是刚接触算法的新手还是刷题刷到怀疑人生的老手看完都应该能对差分形成一套自己的判断框架。2. 差分的本质区间修改如何变成端点修改2.1 从找零钱理解增量思想你去买 8 块钱的东西给了老板 100 块老板要找 92 块。老板有两种做法一种是真一张张数 92 块钱给你另一种是先在账本上记一笔找零 92等结账的时候再统一轧账。第一种适合单次交易第二种适合一天有几百笔交易的情况——如果每笔都当场清点收银台得排队到天荒地老但如果只记账、最后统一结算每笔交易只需记一个数字结算时把账本加起来就行。差分的思路就是第二种。它不追求每次操作后立刻更新数组而是把每个区间操作转换成一种记账——只在区间端点记下变化量最后统一做一次处理把账轧平。这里的轧平在代码里叫求前缀和。2.2 差分数组的定义与构造给定原数组 a下标从 1 开始a [0, a1, a2, a3, ..., an]构造差分数组 d规定d[1] a[1]d[i] a[i] - a[i-1]对 i 从 2 到 n也就是说d 里存的是原数组相邻两项之间的差值。你可能觉得这有啥用一堆正负号能干嘛关键在这里已知 d 求 a 的过程就是前缀和。你看a[i] d[1] d[2] ... d[i]所以差分就是前缀和的逆运算前缀和把数组压缩成累积值差分把数组拆成变化量。现在问题来了如果我给 a 的区间 [l, r] 统一加 c反映到 d 上会怎样2.3 区间修改的差分表现假设原始数组 a差分数组 d。现在执行操作a[l] 到 a[r] 每个元素都加 c。我们只观察差分数组里哪些位置会发生变化在位置 la[l] 变大 ca[l-1] 没变所以 d[l] a[l] - a[l-1] 会变大 c →d[l] c在位置 r1a[r1] 没变如果 r1 na[r] 变大 c所以 d[r1] a[r1] - a[r] 会变小 c →d[r1] - c中间位置 l i ra[i] 和 a[i-1] 都变大 c差值不变 → d[i] 不变你看一个长达一整个区间的操作在差分数组里就变成了两个点的修改。无论区间多长都只改两个数。这就是区间修改转端点修改的全部秘密。等所有操作都记录完了只需要对 d 做一次前缀和就能还原出最终的 a。复杂度从 O(m×n) 降到 O(m n)。2.4 一个反面理解为什么不能用每次暴力更新差分再还原很多人学差分会走进一个误区以为差分数组也要跟着原数组实时更新。如果每操作一次就做一次前缀和还原那复杂度还是 O(m×n)一点没省。差分的精髓在于延迟结算先攒着所有增量信息最后一次性还原。这和我们记账先不付钱、月底统一结清是一个道理。如果你每笔都当场结清那记账的意义就没了。所以请反复提醒自己差分数组的构建可以一次性做完区间修改只碰端点最后统一求一次前缀和。不要中途反复还原。3. 一维差分的基础题型与代码范式3.1 题型一多次区间加后求最终数组这是最经典、也是所有差分题的基础。给定长度为 n 的初始数组可能全零也可能有初值m 次操作每次把 [l, r] 加上 c最后输出完整数组。处理手法分三步。第一步根据初始数组构建差分数组。第二步对每次操作执行 d[l] c、d[r1] - c。第三步对差分数组做前缀和得到操作后的原数组。如果初始数组不为零构建差分时直接用原数组相邻差即可不需要额外初始化成全零再逐个加一遍。这段逻辑写成代码#include bits/stdc.h using namespace std; const int N 100005; long long a[N], d[N]; int main() { int n, m; cin n m; for (int i 1; i n; i) { cin a[i]; d[i] a[i] - a[i-1]; // 构建差分 } while (m--) { int l, r; long long c; cin l r c; d[l] c; d[r1] - c; // 注意 r1 可能等于 n1数组要开够 } for (int i 1; i n; i) { a[i] a[i-1] d[i]; // 前缀和还原 cout a[i] \n[i n]; } return 0; }代码短就三行核心逻辑但每次写完我都建议你手动跑一遍样例确认边界。比如 l 1 时d[1] 会被加上 c这表示区间从第一个元素就开始变化合理。r n 时d[n1] 会减去 c此时数组要开到 n2 才行不然写 d[n1] 直接越界。3.2 题型二区间加多次后多次区间求和如果题目从输出最终数组升级成操作几次后问一次区间和或者先做一堆区间加再来一堆区间查询只靠差分就不够了。思路是把差分和前缀和叠加使用。先对所有区间加操作打上差分标记一次性还原出最终的 a 数组然后对最终的 a 再做一次前缀和得到前缀和数组 s查询区间 [l, r] 的和就用 s[r] - s[l-1] 回答O(1)。这个套路我管它叫差分负责修改前缀和负责查询。两者是天生一对很多人只学了前缀和、又单独学了差分却没意识到它们组合起来的威力。这里有个容易踩的坑如果你先对差分数组做前缀和还原出 a然后又对 a 做前缀和这两步不能合并成对 d 做两次前缀和吗我建议你推导一下。第一次前缀和a[i] a[i-1] d[i]。第二次前缀和s[i] s[i-1] a[i]。如果你用 d 直接做两次累加等于在算带权重的累加得到的并不是想要的区间和的工具数组。所以老老实实分两步不要偷懒。3.3 题型三区间加上等差序列引入二阶差分这是基础题里比较隐蔽的一种变式。操作不再是区间统一加 c而是区间 [l, r] 内第 k 个元素加 k × step或类似等差递增的增量。此时一看题型二里的一阶差分就不够用了——因为一阶差分只能处理所有元素加同一个常数的情况。等差序列的特点是相邻两个位置的增量差恒定为 step这个增量的增量是常数正好落在二阶差分管辖的范围内。具体做法不展开写只指个方向对原数组做两次差分得到二阶差分数组 d2区间等差加会对应到 d2 上最多四个点的修改。当你遇到加的值不是常数、而是随位置线性变化的题目先想二阶差分。不过我要提醒一句这类题在大厂笔试里的出现频率其实不高很多刷题者在这上面花大量时间结果考试反而不考。我的建议是把一维差分、二维差分吃透二阶差分知道原理即可不必死磕偏题。3.4 差分数组在初始化时的一个理解误区我看到过不少讲解将初始化写成原数组 all zeros 的前提下每次区间加 c等效于 d[l] c、d[r1] - c然后让读者自己推到原数组有初值的情况。很多人推到一半就卡住以为初始值还要额外处理。实际上原数组有初值时差分数组的构建就是 d[i] a[i] - a[i-1]区间修改的操作完全相同不需要把初值当作特殊操作分批次加入。因为差分数组本身就完整描述了原数组的所有信息后续区间加只修改端点位置的变化量最后前缀和还原时初值自然就包括在内了。初值、区间加互不干扰这是我当年学了半天才想明白的点写在这里帮你看少走弯路。4. 二维差分矩阵区域修改的容斥写法4.1 为什么二维不能直接照搬一维如果问题升级成给出一个 n×m 的矩阵每次把一个子矩阵所有元素加 c最后输出整个矩阵一维差分是不是直接扩展成二维就完了逻辑方向是对的但实现细节稍有不同。一维区间只有左右两个端点二维子矩阵有四个角。按照一维差分只改端点的思路二维差分应该只在这四个角上做标记。那四个角怎么标记直接填 c 吗不对。你不能简单地四个角都加 c那样搞混了区域归属。正确的做法是参考二维前缀和的容斥原理。4.2 二维差分的四角标记与容斥假设子矩阵左上角是 (x1, y1)右下角是 (x2, y2)差分数组叫 diff。正确的操作是diff[x1][y1] cdiff[x21][y1] - cdiff[x1][y21] - cdiff[x21][y21] c为什么有加有减你可以把它理解为在 (x1, y1) 这个点开始向右向下同时播撒增量 c这个播撒的效果会覆盖整个从 (x1, y1) 到矩阵无穷远处的区域。但题目要求的只到 (x2, y2)所以要在右侧和下方截断。截断时多减出去的区域又被减了两次需要加回来一次——这就是容斥。等我用简单的图式解释一下。想象 diff 做二维前缀和后每个位置的值等于左上角区域所有标记的和。你在 (x1, y1) 加 c那么从 (x1, y1) 向右下方向的整个区域都会因前缀和传播而获得 c。为了只保留到 (x2, y2)在 (x21, y1) 减 c切断竖直方向的传播在 (x1, y21) 减 c切断水平方向的传播。但右下角 (x21, y21) 那块区域被两个方向的减法都影响到相当于被减了两次 c所以最后要再加回 c。4.3 二维差分的构建与还原代码和一维一样如果原矩阵有初值可以先按行构建差分也可以直接用原矩阵相邻差的方式手动构造。但更省事的办法是把赋予初值这件事也当成一次子矩阵加 c 的操作来执行——每个点 (i, j) 的初值 a[i][j] 等价于对子矩阵 (i, j) 到 (i, j) 加 a[i][j]。这样做的好处是你只需要实现一个 add 函数初始化、操作、还原都用同一套代码不容易写错。代码模板const int MAXN 1005; long long diff[MAXN][MAXN]; void add(int x1, int y1, int x2, int y2, long long c) { diff[x1][y1] c; diff[x21][y1] - c; diff[x1][y21] - c; diff[x21][y21] c; } int main() { int n, m, q; cin n m q; for (int i 1; i n; i) { for (int j 1; j m; j) { long long val; cin val; add(i, j, i, j, val); // 初值当单点加 } } while (q--) { int x1, y1, x2, y2; long long c; cin x1 y1 x2 y2 c; add(x1, y1, x2, y2, c); } // 二维差分还原先对每行做前缀和再对每列做前缀和 for (int i 1; i n; i) for (int j 1; j m; j) diff[i][j] diff[i-1][j] diff[i][j-1] - diff[i-1][j-1]; // 此时 diff 数组就是最终矩阵 for (int i 1; i n; i) { for (int j 1; j m; j) cout diff[i][j] \n[j m]; } return 0; }这里还原用到的式子 diff[i][j] diff[i-1][j] diff[i][j-1] - diff[i-1][j-1] 实际上就是二维前缀和公式只是就地覆盖、省一个数组而已。如果你忘了这个公式可以回忆一个事实当前点的值 上方累积值 左方累积值 - 左上角重复计算值 自身标记。4.4 二维差分在实际题中的变体二维差分不仅仅出现在算法竞赛里。比如图像处理中的区域亮度调整、电子表格批量区域填充、游戏地图里某个矩形区域刷怪底层逻辑都是同一套矩形区域批量修改最后统一读取。有些题不是直接给你子矩阵坐标而是给中心点 (cx, cy) 为中心、边长为 k 的矩形需要你先把坐标算成 x1 cx - k/2 等再调用 add。记得先做边界裁剪把超出矩阵范围的部分 clip 掉否则数组越界或者容斥坐标乱掉。我实际写题时发现二维差分最容易出错的地方不是公式本身而是坐标计算x21、y21 在矩阵边缘会到 n1、m1所以 diff 数组至少要开 (n2)×(m2)。很多新手开成 n×m一跑就崩还以为是公式错了。5. 差分最容易翻车的五个边界问题5.1 问题一r1 越界一维差分里 d[r1] - c如果 r n就写到 d[n1]。很多人的数组刚好开成 n 大小运行时报错或者内存越界。我的习惯是数组一律多开两个单位差分大小开 n2二维开 (n2)×(m2)。多几个 int 的空间成本几乎为零但能省掉大量排查越界的痛苦。5.2 问题二下标从 0 还是从 1 开始C 选手通常习惯从 1 开始读入这样 d[l] c、d[r1] - c 的语义最直观。但很多内置数组、Python list 默认从 0 开始此时区间 [l, r] 加 c 应该写 d[l] c、d[r1] - cr1 越界到 n 时不需要也不能写因为最后前缀和只遍历到 n-1。我见过不少人从 0 开始的题硬套从 1 开始的模板结果所有位置的标记全部错位一位。建议你在代码开头就定死一种习惯别混着用。5.3 问题三把端点修改误写成区间内每个位置都修改这是个很诡异但真实存在的错误。有人理解了差分的大方向但代码里写的是 for (int i l; i r; i) d[i] c理由是反正最后要求前缀和。这一写复杂度又回去了而且因为差分标记被重复叠加结果还不对。差分的高效完全建立在只改两个端点上。如果你发现自己写成了循环立刻停下来检查思路。5.4 问题四数据类型溢出差分数组里累计的 c 可能很大前缀和还原后可能超过 int 范围。尤其是多次区间加的 c 累加到同一位置极端情况下 m 次操作叠加值域可能到几亿甚至几十亿。我用 long long 已经是肌肉记忆但偶尔会见别人用 int 然后 WA 在最后一个数据点。排查明明逻辑对但 WA的时候先看数据类型。5.5 问题五离散化场景下不能直接开数组如果区间的 l、r 范围极大比如 1 到 10^9开数组显然不现实。这时候可以把所有操作涉及到的端点收集起来排序去重映射到连续的紧凑坐标上再做差分。注意此时区间加 c需要用离散化后的坐标操作并且在最后还原时每段的实际长度不一定是 1需要乘上该段的长度。这类题已经算差分的进阶用法但你在基础阶段至少要知道有这回事。真正到笔试面试时数据范围往往没那么夸张别被吓到。6. 差分题目如何识别以及后续可以扩展的方向6.1 一道题什么时候该想到差分我的判断标准就三条几乎不会漏判题目描述里有区间或子矩阵操作是所有元素统一加一个值或统一减一个值操作次数多、目标区间范围大暴力复杂度明显不可接受三条同时满足时直接往差分上想。如果还牵扯到多次操作后查询某个前缀信息那基本就是差分 前缀和的组合套餐。反过来如果操作不是统一加一个值而是乘一个值每个位置加不同的函数值差分就不太合适了。那种情况一般交给线段树、分块这类更通用的数据结构当然复杂度也高不少。差分能做的就是这种均匀批量修改的场景理解这个边界你就不容易把差分用错地方。6.2 前缀和、差分、线段树的配合关系拿区间问题做个简单比较工具修改方式查询方式复杂度前缀和不擅长修改O(1) 区间和构建 O(n)查询 O(1)差分O(1) 区间加需要前缀和还原操作 O(1)最后还原 O(n)线段树/树状数组O(log n) 区间加O(log n) 区间和灵活但常数大差分强在大量修改、最终一次性查询的批量场景。如果修改中间穿插着查询差分就施展不开了那得上树状数组或线段树。你把这个关系理清后做题就不会再看见区间就想套线段树了——很多题用数据结构能做但差分更简单更快。6.3 树上差分差分思想的高级延伸如果你已经吃透了一维、二维差分我建议你可以扫一眼树上差分。它的核心思维是一脉相承的树上的路径修改也可以拆成端点操作比如对从 u 到 v 的路径上所有点加 c可以转化为对 u 加 c、v 加 c、LCA 减 c、LCA 的父节点再减 c最终做一次 DFS 汇总。我第一次看到这个转化时挺震撼的——路径这种曲线信息居然也能被压缩成四个点的标记。虽然基础题型总结到二维差分就够应付大部分入门题了但了解树上差分能帮你看清差分思想的生命力凡是批量修改、最后汇总的问题都有差分的影子。6.4 刷题顺序与心态建议最后说说我个人在带新人包括我自己以前学的时候时验证过的刷题顺序先做三分之一维差分的裸题确保闭着眼睛能写出 d[l] c、d[r1] - c 然后前缀和还原再做原数组带初值、多次区间加后求最终数组接着做区间修改 区间查询的复合题最后挑战二维差分的模板题。顺序千万别反过来——有些人一上来就做二维被容斥绕晕后连一维都开始怀疑。差分入门不难难的是把它融入你的条件反射里。我在自己刷题时有个习惯每道题交之前都手动构造一个 n5 的小样例把过程走一遍确认端点标记得对、边界没越界再提交。这个小动作帮我拦下了许多毫无意义的时间浪费。如果你把上面这些边界、体例、识别方法都过了一遍再遇到开头那道题应该能直接反应过来初始全零数组m 次区间加最后输出数组——三行代码的事别去写两重循环了。这就是差分的价值。