差分数组详解：一维与二维区间修改的高效解法

做区间修改类的题最烦的莫过于“把某个区间里的每一个数都加同一个值”这种操作。我第一次遇到时老老实实写了个双重循环数据量一大直接超时。后来学会差分才明白这种问题根本不需要真去改区间里的每个元素——把变化记在端点上的两个标记里最后用一次前缀和就能还原整个数组。差分说白了就是相邻两项的差并没有多高深但它是解决“区间修改、单点查询/最终还原”这类问题的第一块敲门砖。这篇文章我打算从差分的定义讲起把一维、二维差分的原理和代码都拆开讲透再整理几种我刷题过程中高频出现的基础题型给刚接触这个知识点的同学一份可以直接照抄的笔记。如果看到这里你还不太清楚差分能用在什么地方不妨先记住一句话凡是“多次给区间/子矩阵整体加一个值最后再求结果”的题目都可以优先往差分上想。它能让原本是 O(nm) 的操作复杂度降到 O(nm)n 是数组长度m 是操作次数这个提升在竞赛和面试题里往往是能不能通过的关键。1. 差分到底在解决什么问题1.1 先看朴素做法的痛点假设现在有一个长度为 n 的数组初始全是 0。接下来有 m 次操作每次操作形如“把 [l, r] 这个闭区间里的所有数都加上 v”所有操作结束后要求输出整个数组。最直接的写法是这样for (int i 1; i m; i) { int l, r, v; cin l r v; for (int j l; j r; j) { a[j] v; } }这段代码本身没有任何问题问题出在复杂度上。一次操作的代价是 O(r - l 1)最坏情况下每次操作都是对整个数组那么总代价就是 O(nm)。当 n 和 m 都到 10^5 甚至 10^6 量级时这个复杂度是无论如何都跑不完的。那能不能不遍历区间里的每个元素当然可以。你真正要改变的并不是区间内部每个位置的“状态”而是整个区间相对于它左右两侧的“变化”。换句话说区间内部相邻元素之间的差值根本没有变变的只有区间左端点处和右端点之后那两处的差值。差分就是专门用来“记录这种差值变化”的工具。1.2 差分的定义和第一层理解给定数组 a[1..n]定义一个差分数组 d使d[i] a[i] - a[i-1]其中约定了 a[0] 0。那么反过来很容易得到a[i] d[1] d[2] ... d[i]也就是说对差分数组做前缀和就能还原出原数组而对原数组做差分就能得到差分数组。差分和前缀和在数学上是互逆的一对操作这也解释了为什么还原差分时需要做一次前缀和。可以拿日常的记账来类比。a 数组是每一天的账户余额d 数组则是“今天比昨天多花了多少”。如果你在一段时间内每天固定多花一笔钱那么从这段时期开始的那一天起“今天比昨天多花的钱”会突然增加到这段时期结束后的下一天又恢复原状。中间每一天的差值变化量都是 0。差分记录的就是这个“变化量”在哪些位置上发生了突变。理解了这层关系就能理解为什么区间加可以转化为差分数组上的两次单点修改。这部分是全文最核心的内容下一节我详细说说。2. 一维差分原理、代码与边界2.1 区间加如何变成两个单点修改还是那个问题对区间 [l, r] 内的每个元素加 v。看差分数组 d 的定义d[i] 只和 a[i]、a[i-1] 有关。区间加 v 之后a[l] 增加了 v而 a[l-1] 没变所以 d[l] 增加了 v区间内部l1 到 r的每个位置当前项和前一项都同时增加 v差值不变所以 d[l1..r] 全部不变a[r1] 没变而 a[r] 增加了 v所以 d[r1] 减少了 v。因此一次区间加操作等价于d[l] v; d[r 1] - v;注意这里并没有真正去修改区间内部的任意一个值只是修改了两个位置。这就是“差分能做到 O(1) 修改”的底气所在。至于区间内部那些元素等你最后需要原数组时对 d 做一次前缀和就全部还原了。2.2 代码实现和还原过程完整的模板代码非常短建议直接背下来当作肌肉记忆#include bits/stdc.h using namespace std; const int N 100005; long long a[N], d[N]; // 原数组和差分数组用 long long 防溢出 // 区间修改[l, r] 每个数增加 v void add(int l, int r, long long v) { d[l] v; d[r 1] - v; } 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 v; cin l r v; add(l, r, v); } // 对差分数组做前缀和还原出最终数组 for (int i 1; i n; i) { a[i] a[i - 1] d[i]; cout a[i] (i n ? \n : ); } return 0; }实际操作里有两点很容易踩坑第一d 和 a 的数组长度最好开到 n2而不是 n。因为add里会出现d[r1]当 r 恰好等于 n 时就会访问到 d[n1]。如果数组开小了就悄悄越界在本地跑可能没事到了在线评测系统就莫名其妙崩掉或者答案出错。第二前缀和还原时要用a[i] a[i-1] d[i]有人会写成a[i] a[i] d[i]然后发现结果完全不对。仔细想想a[i]的原值已经被覆盖了这里需要的是逐项累加的过程而不是原地叠加。2.3 初始化差分数组的另一种理解方式很多教材介绍了“直接求相邻差”的初始化方法d[i] a[i] - a[i-1]。还有一种写法初看不那么直观但非常有助于深入理解差分的本质。就是把差分数组全初始化为 0然后对每个位置 i 执行一次add(i, i, a[i])。为什么这样也能初始化成功因为add(i, i, a[i])等价于“给区间 [i, i] 这个长度为 1 的区间加上 a[i]”。把 n 个单点区间操作叠加在一起最后对 d 做前缀和得到的就是原数组 a。这种写法的好处在于它把“初始数组”也统一成了一次次区间修改操作代码逻辑变成了一套模板走天下for (int i 1; i n; i) { int x; cin x; add(i, i, x); }我个人建议两种初始化方式都掌握。做题时用第一种节省时间理解时用第二种更通透——你会在潜意识里把“初始值”和“后续修改”看成同一件事这对后面学二维差分尤其重要。3. 二维差分矩形加法的容斥之美3.1 从一维到二维的自然推广一维差分处理的是区间二维差分处理的就是子矩阵。题目常常长这样给定一个 n×m 的矩阵初始全 0有 q 次操作每次操作把左上角 (x1, y1) 到右下角 (x2, y2) 这个矩形区域内的所有元素加 v最后要求输出整个矩阵。暴力的做法又是四重循环复杂度 O(q·n·m)。数据量一大就得换思路。我们沿用一维的经验矩阵内部的相对差值不变变的只是矩形的四条边界处。二维差分的定义也会自然地变为d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]这个式子看起来有点绕但仔细看会发现它就是二维前缀和的逆运算。只要对 d 做一次二维前缀和就能还原出 a。你可以先接受这个定义然后看一个更漂亮的结论一次矩形加操作在差分矩阵 d 上只需要修改四个角。3.2 四个角标记的推导与代码结论先摆出来。要把左上角 (x1, y1)、右下角 (x2, y2) 的矩形整体加 v对应的差分修改是d[x1][y1] v; d[x21][y1] - v; d[x1][y21] - v; d[x21][y21] v;解释一下为什么是这四个位置。先想一维区间 [l, r] 加 v需要在 d[l] 加 v、d[r1] 减 v一正一负两个点。二维是把两个方向叠起来所以每个方向都要有正负配对(x1, y1) 是矩形的左上角作为整个增加的起点所以是正号到了 (x21, y1) 这一行说明 y 方向还没结束但 x 方向已经超出矩形下边界了所以在这里要减掉到了 (x1, y21) 这一列说明 x 方向还在矩形内但 y 方向已经超出右边界也要减掉而 (x21, y21) 这个点被前两步减了两次实际上多减了一次所以需要再加回来。这个“多加一次再补回来”的过程就是典型的容斥原理。如果还不放心可以拿一个 3×3 的小矩阵手动推一遍给 (1,1) 到 (2,2) 的矩形加 1把上述四个位置的标记写出来再做二维前缀和看结果是不是恰好那个矩形内全为 1。我每次给新人讲二维差分都会建议他们亲手推一遍这个例子推完就再也不会记错四个点的符号了。代码模板const int N 1005; long long d[N][N]; // 子矩阵加 v左上角 (x1, y1)右下角 (x2, y2) void add(int x1, int y1, int x2, int y2, long long v) { d[x1][y1] v; d[x2 1][y1] - v; d[x1][y2 1] - v; d[x2 1][y2 1] v; } // 还原原矩阵二维前缀和 for (int i 1; i n; i) { for (int j 1; j m; j) { d[i][j] d[i - 1][j] d[i][j - 1] - d[i - 1][j - 1]; } }还原那一步的递推式也是容斥当前格等于上方累加、左方累加再减去左上角重复累加的部分。和一维的a[i] a[i-1] d[i]是同一套思想只是多加了一个方向。3.3 二维初始化与常见坑二维差分数组的初始化也有两种思路。如果原矩阵有初始值最稳妥的方法是先把矩阵读进 a 数组然后按d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]初始化。如果矩阵初始全为 0那就更简单了直接把 d 数组清零每次操作都调用 add 即可。还有一点需要提醒矩阵的行列下标都是从 1 开始数组至少要开到 n2 行、m2 列。因为 add 里会出现 x21 和 y21当 x2n、y2m 时就会访问到 d[n1][m1]。这个维度开小了在线评测系统上报错的方式往往非常诡异。另外如果数据范围大建议全程使用 long long二维前缀和的累加量有时候会超出 int 的范围这种溢出错误很隐蔽不容易排查。4. 基础题型总结从模板到组合4.1 直接在模板上修改区间加与最终还原这种题型最基础也最直观就是开头提到的场景——所有操作输入完成后输出最终数组。只要背下 add 函数和最后一次前缀和的代码再注意一下数组边界基本就是送分题。但要注意一种变体题目不给“输出整个数组”而是问你某个位置最终是多少。这种“多次区间加 单点查询”的问题其实也是差分的老本行。做法就是先离线把所有 add 操作处理完最后做前缀和时只算到目标位置为止。不需要真的扫描整个数组也不需要线段树复杂度 O(nm) 就解决了。如果你看到题面描述里有“区间修改”和“单点查询”这两个关键词先想想差分很多题比你想的简单。4.2 差分 二分答案批量操作的可行性判断有一类经典题大概意思是有若干个资源位置每个位置有容量上限接下来有一系列按顺序执行的操作每个操作会占用一段连续区间内的一部分资源。问从第几个操作开始会出现“某个位置的资源超限”。如果老老实实逐个操作模拟每次都要更新区间并检查最大值复杂度会很高。正确的打开方式是二分答案二分操作数量 k然后只执行前 k 个操作用差分数组把这些操作的修改全部打上标记再前缀和还原检查是否存在超过上限的位置。如果前 k 个操作没问题说明答案在右边否则在左边。这种题的复杂度是 O((n m) log m)比模拟快一个数量级。注意每次二分复现前 k 个操作时差分数组一定要重新清空或重新初始化不然上一次二分的残留标记会把结果污染掉。我见过不少人在这个细节上翻车排查半天发现是差分数组没清干净。4.3 正负配对思想区间加变全体相等这是差分一个非常优雅的应用问法通常是给定一个数组每次操作可以选择一个区间让区间内所有数同时加 1 或同时减 1求最少多少次操作能让整个数组所有元素相等最终值任意。朴素想法完全无从下手但用差分看就非常清晰。设 d[i] a[i] - a[i-1]并且令 a[n1] 0那么一次对 [l, r] 的 1 操作等价于 d[l] 加 1、d[r1] 减 1。也就是说一次操作的本质是把差分数组里的一个“1”和一个“-1”配对消掉一部分。要让数组最终所有元素相等就等价于让 d[2..n] 全部变成 0因为相等的数组相邻差值全为 0而 d[1] 和 d[n1] 会自动变成互为相反数正好表示最终值相对初始值的变化量。于是问题变成了差分数组中 d[2..n] 这一段的正数总和是多少、负数绝对值总和是多少。每操作一次就相当于把一个正数和负数配对。答案就是这两个数的较大值P sum_{i2..n} max(d[i], 0) Q sum_{i2..n} max(-d[i], 0) ans max(P, Q)随手验证一个例子。a [1, 2, 2, 1]则 d [1, 1, 0, -1, -1]其中最后一个是 -a[n]。d[2..4] 的正数总和是 1负数绝对值总和是 1答案是 1 次操作把区间 [2, 3] 同时减 1数组就变成 [1, 1, 1, 1]。这个例子虽然简单但足以体现“操作次数 正负配对次数”的核心思想。4.4 等差数列的区间加二阶差分还有一种稍微进阶的题目每次操作不是加同一个值而是给区间 [l, r] 加上一个首项为 s、公差为 d 的等差数列。比如给 [3, 6] 加上 1、3、5、7首项 1公差 2。一阶差分处理不了这个因为区间内部相邻两项的差值不再是 0而是固定的公差 d。思路是再差分一次用二阶差分先对原数组做一阶差分得到数组 b。给区间 [l, r] 加首项 s、公差 d 的等差数列等价于在 b 上做这样几个操作b[l] s; 对 b[l1..r] 整体加 d; b[r1] - s (r - l) * d;然后再对 b 做一次差分得到 c。因为 b 上的“区间加 d”又是一次一维差分操作所以合并之后 c 上只剩四个单点修改c[l] s; c[l1] d - s; c[r1] - s (r - l 1) * d; c[r2] s (r - l) * d;最后对 c 做两次前缀和先还原 b再还原 a。这个公式看起来有点复杂但推导逻辑是清晰的两层嵌套第一次差分处理“等差数列整体”带来的首项变化第二次差分处理“公差”造成的区间均匀变化。如果需要记住建议用小数据推一遍比死记公式可靠得多。5. 常见错误与调试经验汇总最后把我这些年踩过的坑集中整理一下很多都是新手很容易犯的共性问题。关于数组越界。差分操作里必然会出现 r1、x21、y21 这类下标所以数组一定要比“看起来需要的尺寸”多开 1 到 2 个位置。一维开 n2二维开 (n2)×(m2)。千万别节省这一点点空间。关于忘记还原前缀和。差分数组记录的是变化量不是最终值。做完所有修改之后一定记得做前缀和二维就是二维前缀和才能得到原数组。漏掉这一步输出的会是一堆“标记”看起来完全不是答案。排查时先确认是不是漏掉了这一步这是高频低级错误。关于单次操作写错端点。区间 [l, r] 加 v写的是d[l] v; d[r1] - v;常有新手把 r1 写成 r结果发现区间右端点处数值异常。建议在纸上画一条线段标出修改前后 d 的变化这个错误就能一眼看出来。关于二维差分四角的符号。我的记忆口诀是“开始为正、结束为负、角落回加”。左上角是开始加下边界和右边界是结束减右下角被减了两次加回来。关于二分加差分的现场还原。二分次数 k 时差分数组每次都要从头清零重新打标记。不要复用上一轮二分的结果否则检查会出错。可以把 add 操作预先存进结构体数组每次二分只处理前 k 个。关于数据类型的溢出。如果题目的数据范围达到 10^9 量级m 次操作之后每个位置的累加量很容易超过 int 的范围。直接全部用 long long最多省几个字节但能避免非常难查的溢出问题。调试差分题还有一个很实用的技巧先用一个小的随机样例跑暴力解法和差分解法把两个结果逐行对比。这种对拍方式不需要多复杂的工具几行代码就能写出来。差分本身就是线性操作如果出现不一致问题几乎一定出在边界下标或者符号上仔细检查就能定位。我个人复盘下来差分这个知识点真正的价值不在于它有多难而在于它提供了一个“用端点变化代替区间扫描”的思考方向。很多区间相关的算法题最后都能化归到差分上来。把这套基础打牢后面再遇到线段树、树状数组这些更重的数据结构时你也会多一层对比的视角理解它们各自擅长的场景。希望这篇总结能帮你跨过差分这道门槛。