差分算法这个东西我在算法竞赛和日常开发里用过很多次每次用都觉得很巧妙明明是对一个区间做修改最后却只动了几个点的值等到最后统一算一次前缀和所有区间操作一次性“兑现”。这种延迟计算的思路在代码里省出来的不只是时间更是一种对问题建模的直觉。一维差分、二维差分加上很多人一听就懵的“差分隐私”我一次性讲透。这篇内容适合谁刚接触算法的同学刷题卡在区间修改的选手以及写业务代码时需要在批量数据上做范围加法的开发者。读完你能掌握差分数组的构建、区间修改的通法、二维场景下的四角操作以及差分思想和其他领域的边界比如那个名字很像但完全不是一回事的“差分隐私算法”。1. 差分算法的本质把区间操作变成点操作1.1 为什么朴素做法慢以及差分的核心思路先看一个非常常见的问题你有一个长度为 n 的数组初始值已知现在有 m 次操作每次把区间 [l, r] 内的每个元素都加上一个数 v。操作全部结束后输出每个位置最终的值。最直观的写法就是一个循环从 l 遍历到 r逐个加 v。当 n 和 m 都到 10^5 这个量级最坏情况是 10^10 次操作在普通机器上就是几秒到十几秒的耗时在竞赛环境里妥妥超时。为什么慢因为你的修改强度和区间长度成正比一个区间越长一次操作越贵。差分算法的思路一句话就能概括我不直接修改区间内的每个元素而是修改一个辅助数组上极少数的几个点让这些“点修改”在最后做一次前缀和时自动还原出所有区间修改的效果。这正是“懒”的智慧——把所有区间修改延期结算最后一口气处理完。用生活场景比喻一下。想象你是一个班级的班主任要通知第 3 到第 10 个座位上的同学去领教材。朴素做法是挨个喊 8 个人差分做法的思路是你在第 3 个座位贴一张“从这里开始每个同学都去领书”的纸条再在第 11 个座位贴一张“到这里为止后面的不用去”的纸条。最后你从头走一遍看到“开始”纸条就进入“领书状态”看到“结束”纸条就退出。所有同学是不是该领的都领到了这就是差分。差值的思想其实和微积分里的导数和积分有几分神似数组是“原函数”差分数组是“导数”做一次前缀和就相当于“积分”还原。这个类比不是强行拔高而是真的有用——你理解了差分的逆运算就是前缀和后面很多变式都能顺理成章地推出来。1.2 一维差分数组的构建与还原一维差分数组的定义非常朴素设原数组为 a差分数组为 b那么 b[i] a[i] - a[i-1]。比如 a [2, 5, 1, 8, 3]那么 b[1] a[1]因为 a[0] 当作 0b[2] a[2] - a[1] 3b[3] a[3] - a[2] -4b[4] a[4] - a[3] 7b[5] a[5] - a[4] -5。得到 b [2, 3, -4, 7, -5]。这个数组有个神奇的性质对 b 做前缀和也就是 s[i] b[1] b[2] ... b[i]你会发现 s 恰好等于 a。这不是巧合而是差分定义的直接推论。差分和前缀和互为逆运算就像乘法和除法一样。你可能会问既然 b 就是从 a 推出来的那它有什么用关键就在区间修改这一步。当你要给 [l, r] 区间内每个元素加 v 时只需要做两个操作b[l] vb[r1] - v然后对 b 求一遍前缀和得到的结果就是修改后的数组 a。为什么这样有效因为 b[l] 加 v 之后从位置 l 开始的前缀和都会凭空多出 v一直到 b[r1] 减掉 v从 r1 开始前缀和又恢复正常。这就像在水管上打开一个阀门注水水流到某个位置再关掉中间那段的水位就抬高了。有一个细节必须注意b[r1] 可能需要访问到 n1 这个位置。所以差分数组在声明时至少要留出 n2 的空间不是 n 也不是 n1而是 n2。为什么因为当 r n 时你需要操作 b[n1]下标 n1 要合法。这个边界问题我见过无数人栽跟头后面会专门讲。2. 一维差分实战区间修改问题的标准解法2.1 经典场景区间加与最终查询竞赛里最标准的差分题长这样n 个数的数组m 次区间加操作最后输出完整数组。完整代码不长但每一步都有讲究。#include bits/stdc.h using namespace std; const int N 100005; long long a[N], b[N]; int main() { int n, m; cin n m; // 读入原数组同时构造差分数组 for (int i 1; i n; i) { cin a[i]; b[i] a[i] - a[i - 1]; // 差分定义 } // 处理 m 次区间修改 while (m--) { int l, r, v; cin l r v; b[l] v; // 区间起点开始生效 b[r 1] - v; // 区间终点之后撤销 } // 对差分数组求前缀和还原最终结果 long long cur 0; for (int i 1; i n; i) { cur b[i]; a[i] cur; cout a[i] ; } cout endl; return 0; }这里的核心在于所有区间修改根本没有直接动原数组 a而是往 b 上打标记。等到所有操作都处理完才通过一次前缀和把 b 还原成新的 a。再强调一次这个过程是 O(n m)把原来可能 O(n*m) 的暴力降到了线性级别。如果 n 和 m 都是 10^5暴力要 10^10 次差分只要 2×10^5 次差距是五万倍。有些刚接触的读者可能会困惑为什么 b[i] a[i] - a[i-1] 这个构造方式和“区间加”做法里 b[l] v、b[r1] - v 看起来不太一样其实两种方式可以统一。你可以把初始数组 a 想成是 n 次“长度为 1 的区间加操作”叠加出来的区间 [i, i] 加上 a[i]。用差分操作来写就是 b[i] a[i]b[i1] - a[i]。这恰好等价于 b[i] a[i] - a[i-1]。所以构建差分数组本质上就是在做 n 次单点区间加。想通这一点你就真正理解了差分的递归性。2.2 差分与前缀和的配合从“最后总结果”到“过程查询”上面的写法能解决“全部操作结束后输出最终数组”的问题。但有的时候题目要求不只是最终结果而是“每次操作之后当前数组的样子”。这种情况差分还灵吗直接说结论不灵了。差分擅长的是“多次修改、一次查询”如果要“多次修改、多次查询”你需要的是树状数组或线段树它们能在每次操作后以 O(log n) 的代价查询单点或区间的当前值。差分的优势是一次性离线处理。遇到在线查询的题目强行用差分每次查询都重新算前缀和复杂度变成了 O(nq)反而不如线段树。这其实引出一个重要的建模判断看到区间修改先问自己“查询发生在什么时候”。查询全部发生在修改之后——差分。查询穿插在修改之间——线段树或者树状数组配合差分的变体。还有一种混合用法很常见先用差分数组快速处理完所有区间修改得到最终数组然后再对最终数组做一次前缀和得到前缀和数组用来 O(1) 回答“区间 [l, r] 的总和是多少”。这个场景在离线统计里出现频率非常高。差分负责“修改”前缀和负责“查询”两者配合天衣无缝。本质上是把两道逆运算连成一个环差分 - 前缀和还原数组 - 再前缀和得到可查询的累积和。2.3 一维差分的高阶变式差分不是只能处理“区间加一个常数”稍微变形就能处理“区间加一个等差数列”。比如某次操作是“区间 [l, r] 内每个位置 i 加上 ki c”其中 k 和 c 是常数。这时你可以开两个差分数组一个记录常数项 c 的区间加另一个记录斜率项 ki。斜率项的差分操作有点巧对位置 i 加 k*i 等价于“在差分数组上做两次差分”。具体来说开一个数组 d1 记录“加 k”的操作另一个数组 d2 记录“加 k*ic”的操作。每次区间加等差数列执行d2[l] cd2[r1] - c常数项d1[l] kd1[r1] - k斜率起始最后还原时先对 d1 做前缀和得到每个位置的斜率贡献 k_i再对 d2 做前缀和得到常数贡献最后答案 a[i] k_i * i c_i这里相当于对差分数组再做了一次差分也就是“二阶差分”的思路。理解的关键在于一次差分把区间加变成两个点的操作那么“斜率和 i 相乘”这种随下标线性增长的操作就需要差分两次才能用常数个点表示。想在竞赛里拿高分这种二阶差分值得吃透虽然考题不算多但一旦出现就是区分度所在。3. 二维差分从线到面的推广3.1 二维差分数组的构建一维差分解决的是“线上的区间修改”二维差分解决的是“面上的子矩阵修改”。问题场景变成这样给你一个 n 行 m 列的矩阵初始值已知有 q 次操作每次把子矩阵 (x1, y1) 到 (x2, y2) 内的所有元素加上 v全部操作结束后输出整个矩阵。一维差分的核心是 b[i] a[i] - a[i-1]二维差分要对行和列分别做差。定义二维差分数组 diff使得对 diff 做二维前缀和后能得到原矩阵 a。二维前缀和的公式是sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] a[i][j]这个公式是二维前缀和的“容斥原理”加左边、加上边减左上角因为被加了两次。差分是前缀和的逆运算所以二维差分数组的构建也遵循容斥的思路diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]你会发现它和前缀和公式是镜像对称的。如果你已经掌握了二维前缀和的容斥写法二维差分其实就是把它倒过来写理解成本会低很多。实操中构建二维差分数组最常用的方式反而是“用修改操作本身来构建”也就是把初始矩阵 a 看成 n*m 次单点操作每次给点 (i, j) 加上 a[i][j]。这样就不用单独写构建公式而是调用子矩阵修改的函数来逐个加点。这种“统一用操作建数组”的思路代码更简洁也不容易搞混公式。3.2 子矩阵区间修改核心公式推导一维区间加的操作是 b[l] v、b[r1] - v两个点。二维子矩阵加的操作是四个点这也是很多初学者最容易记错的地方。直接给出公式前先用直觉推导一下。假设要给子矩阵 (x1, y1) 到 (x2, y2) 内的所有元素加 v我们需要在 diff 上做四次修改diff[x1][y1] vdiff[x21][y1] - vdiff[x1][y21] - vdiff[x21][y21] v为什么是这四个点拆开看。diff[x1][y1] 加 v做二维前缀和时从 (x1, y1) 开始向右下方向的整个矩形区域都会加上 v这个范围太大了。需要把超出的部分减掉向下超出目标区域所以 diff[x21][y1] 减 v把 x2 行以下的影响消掉向右超出所以 diff[x1][y21] 减 v把 y2 列以右的影响消掉。但这两个减法在右下角 (x21, y21) 交叉重叠多减了一次 v要加回来。所以就有了第四个点 diff[x21][y21] v。这个推理过程请务必自己画一个 6×6 的网格图手动标一遍。我第一次学的时候死记硬背结果每次位置都记混后来画了三次图“右下一加”这个操作就再也没错过。在这四个点之外其他位置不做任何修改。等最后求一遍二维前缀和子矩阵内所有元素统一加上 v子矩阵外的区域完全不受影响。注意这里的 x21 和 y21 也可能越界所以二维差分数组至少要开 (n2) 行、(m2) 列。有些题目 n 和 m 都是 1000数组开 1005×1005 就够用但如果你偷懒开成 1000×1000遇到 x2 n 的情况直接越界程序崩溃都是小事更隐蔽的是越界读取不报错给你返回一个随机数字导致结果错得莫名其妙。3.3 二维差分代码实现与注意事项直接上一个完整可跑的二维差分解法处理“矩阵初始值 q 次子矩阵加 输出最终矩阵”#include bits/stdc.h using namespace std; const int N 1005; long long a[N][N], diff[N][N]; // 子矩阵加 v左上角 (x1,y1)右下角 (x2,y2) void add(int x1, int y1, int x2, int y2, long long v) { diff[x1][y1] v; diff[x2 1][y1] - v; diff[x1][y2 1] - v; diff[x2 1][y2 1] v; } int main() { int n, m, q; cin n m q; // 读入初始矩阵用单点加的方式构建差分数组 // 单点 (i,j) 加 val 等价于子矩阵 (i,j)-(i,j) 加 val for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; add(i, j, i, j, a[i][j]); } } // 处理 q 次子矩阵加 while (q--) { int x1, y1, x2, y2; long long v; cin x1 y1 x2 y2 v; add(x1, y1, x2, y2, v); } // 二维前缀和还原最终矩阵 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]; a[i][j] diff[i][j]; cout a[i][j] (j m ? \n : ); } } return 0; }有几个容易错的细节要单独拎出来说。第一构造差分数组时我用的方式是“单点加”也就是把初始值的每个元素当作一次子矩阵加操作。这样做不用单独写 diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1] 这个公式代码可读性更高函数复用也更干净。实测下来效率几乎没差别因为单点加的调用次数就是 n*m 次和构建差分数组的复杂度一样。第二还原时直接在 diff 原数组上做二维前缀和覆盖式更新。如果你后续还要用到原始的 diff 值那得另开数组保存但这个场景里 diff 还原后就是最终矩阵原地更新没问题还省内存。第三注意类型。矩阵数值和修改量累加之后可能超过 int 范围竞赛题尤其爱卡这个直接用 long long 最稳妥。内存上1005×1005 的 long long 数组大约是 8MB开两个就是 16MB多数平台都完全能接受。4. 差分思想的应用延伸从静态批量修改到差分隐私算法4.1 差分的边界应用多次修改一次查询的应用场景差分算法的应用场景比看起来要广。比如经典的“航班预订统计”类业务问题一组航班编号从 1 到 n有若干条预订记录每条记录代表“从第 i 天到第 j 天每天增加 k 个座位”最后要输出每天的总座位数。这不就是区间加吗用差分一次搞定。再比如“拼车旅程统计”每个行程是“从 start 到 end 上车 drop 人”统计每个站点的车上人数。把上车点当作区间起点加人数下车点当作区间终点后减人数最后前缀和就是每个站点的人数曲线。差分思想在真实业务里的落地非常自然。还有一类“树上差分”的问题适合已经掌握数组差分的读者进一步研究。树上差分处理的是“树上路径修改、最后统一查询”的问题核心思路是把一条路径的修改拆成四个点的修改最后做两遍 DFS 前缀和还原。这个拓展说明差分思想不止限于数组和矩阵只要结构上有“前缀和”的逆运算差分就能用。树上的“前缀”就是根到节点的路径和“差分操作”就是把路径修改转成 O(log n) 甚至 O(1) 的点修改。理解到这一层你在算法上就算真正“入了差分的大门”。我个人在实际做题中还发现一个好用的小技巧当题目给了多个区间操作但又要求最后输出所有位置的累计值时不要急着想数据结构先试试差分。很多看起来很唬人的区间操作题目最后就是个差分的壳。怎么判断你只要确认“修改量只增不减、查询只发生在最后”几乎都可以先差分为第一候选方案写起来快不容易错调试也容易。4.2 差分隐私算法名字像但本质不同搜“差分算法”的时候很多人会被“差分隐私算法”这个词带跑。这里必须郑重澄清差分隐私Differential Privacy和你前面看的数组差分完全是两个世界的概念只是中文翻译里都带了“差分”两个字。差分隐私是数据隐私保护领域的一种技术框架最早由 Dwork 等人在 2006 年提出解决的核心问题是当数据分析师查询一个数据库的统计结果时如何保证查询输出不会泄露任何一位个体用户的具体信息它的做法是在查询结果中注入经过精心设计的随机噪声使得攻击者无论怎么对比输出结果都无法判断某一条数据是否真的在原始数据库里。常用的机制包括拉普拉斯机制针对数值查询和指数机制针对非数值查询。这里的“差分”指的是“只有一个个体数据不同”的两个相邻数据集要求它们的查询输出分布足够接近。两者的根本区别在哪里算法里的差分是对原始数据做“相邻元素求差值”核心是线性计算技巧目的是加速区间操作差分隐私里的“差分”是比较两个数据集在查询输出上的概率分布差异核心是随机性和概率论目的是隐私保护。一个用在加速运算一个用在防止泄露没有任何直接关联。为什么会有这种命名混淆因为英文里确实都不带前缀修饰——一个是 difference array差分数组一个是 differential privacy差分隐私中文都译成了“差分”。所以如果你看到一篇技术博客讲“差分算法”结果突然开始讲拉普拉斯噪声别懵大概率是标题蹭了热度混装了内容。我写这个节目就是想帮你把这两个名字的边界划清楚以后在社区看到相关讨论时能迅速分辨对方在聊哪个“差分”。那有没有什么联系硬要说的话有一种“差分隐私 算法竞赛”结合的可能场景在某些联邦学习或统计发布的轮次中需要先对数据做聚合统计类似差分数组做的事情再在发布结果时加噪声差分隐私做的事。这只是业务上的串联不是算法上的融合。把这两个概念彻底分开比在技术上硬找它们的共同点要有用得多。5. 常见问题与排查技巧实录5.1 下标越界r1 和 n1 的边界陷阱差分数组最经典的 bug 就是越界。一维的情况下当操作区间是 [l, r] 时你要操作 b[r1]。如果 r 恰好等于 n那么 b[n1] 就是越界访问。解法很简单数组开成 n2 大小。这个“2”不是玄学是给 b[r1] 留出来的合法位置。二维差分同理add 函数会访问 diff[x21][y1]、diff[x1][y21]、diff[x21][y21]所以数组至少要开 (n2) × (m2)。很多人开成 (n1) × (m1)以为够了结果 x2 n 时 x21 n1刚好越界一格。别的语言可能直接抛异常还好说C 这种越界不报错的语言最坑你拿到一个脏值程序继续跑最后答案全错而且错误极其隐蔽。排查这类问题有个经验只要用差分声明数组时就不用脑子地开 n5、m5或者直接用 N 和 M 的常量多开几个单位。多浪费的几 KB 内存换来的是调试时间的巨大节省这笔账怎么算都划算。5.2 还原时忘记前缀和或者前缀和公式写错区分差分数组和原数组是理解这道题的关键。操作阶段改的都是 diff原数组 a 一直没动过。所有操作完成之后必须对 diff 做前缀和才能得到最终的 a。漏掉这一步你输出的是半成品 diff结果当然对不上。二维场景下前缀和公式特别容易写错。正确写法是 diff[i][j] diff[i-1][j] diff[i][j-1] - diff[i-1][j-1]。注意最后是减一次 diff[i-1][j-1]因为被加了两次而且这个公式是在 diff 数组上就地更新的。有些同学喜欢另开一个 sum 数组来还原那就要小心diff[i][j] 的原始值和 sum[i-1][j] 的更新顺序容易搞混不如就地更新来得干净。验证差分写没写对有一个高效的测试方法手工构造一个小数据。比如 1×3 的一维数组 [0, 0, 0]给它做两次区间加然后手推预期结果再跑代码对比。如果连小数据都能错那就是基本逻辑没理清小数据对大数据错再考虑边界和类型问题。5.3 整数溢出与二维数组初始化区间累加的数值在多次操作之后很可能超过 int 上限。比如 n、m、q 都是 10^5每次加的 v 也是 10^5累积值就能到 10^10int 只有 2×10^9必炸。所以差分数组尤其涉及累加和前缀和还原的数组一律用 long long。这个习惯越早养成越好几乎每个用差分的选手都因为 int 溢出吃过亏。二维数组初始化也有讲究。如果你开了局部数组C 不会自动清零必须手动 memset 或定义为全局变量。定义在全局的数组会零初始化这是很多人喜欢把大数组放全局的原因之一。如果你偏好动态开辟二维 vector记得 vector vector diff(n2, vector (m2, 0)) 的初值显式给 0不然就是未定义行为。5.4 差分的“一次性”局限什么时候不要硬用差分差分算法的时间优势建立在“只做一次最终还原”这个前提上。如果题目要求每次操作后立刻查询某个位置的当前值你还能用差分吗简单硬用的话每次查询都要重新跑一遍前缀和复杂度退回到 O(nq) 甚至更高和暴力没什么区别。遇到这种需要在线查询的情况正确打开方式是线段树区间修改区间查询、树状数组加差分技巧区间修改单点查询本质是用树状数组维护差分数组让“修改 O(log n)、查询 O(log n)”变成现实。树状数组 差分是很有意思的组合它和纯差分的区别是不必等到最后一次性还原而是随时能查单点值。这本质上还是在用差分思想只不过把“最后统一前缀和”换成了“树状数组动态维护前缀和”。所以做算法题选型时我的习惯流程是先看修改次数 q 和数据规模再看查询时机最后决定是不是差分。不要在题目只给了“在线查询”字样时无脑上差分那是对差分能力边界的误解。把边界弄清楚比背更多模板更重要。差分是一把快刀但它的刃口只在一个特定方向上最好使——离线、批量、最后统一出结果这三个词就是它的舒适区。在这个舒适区里它几乎无敌出了这个圈就该轮到其他数据结构上场了。说到这我想把最后一条心得留给你学差分不要只背操作公式试着把它理解成“延迟计算 逆运算还原”这两个思想的组合。数组差分是区间修改的前缀和逆运算二维差分是子矩阵修改的二维前缀和逆运算树上差分是路径修改的“根到节点路径和”的逆运算。你只要抓住了“前缀和的逆运算”这把钥匙就会发现各种各样的差分变式不过都是同一个套路换了不同的数据结构外壳。真正值钱的不是你背下了 add 函数那几行代码而是你面对一个区间操作问题时能一眼看穿它“能不能用差分”的眼光。