如果你刷过题或者搞过OI大概率见过这种局面给一个数组要快速完成“把[l, r]区间统一加上某个值”的操作最后再问你某些位置最终是多少。如果每次都暴力循环复杂度O(nm)数据一大直接超时。这时候一维差分算法就是最经典的解药——它能把每次区间操作压到O(1)最后统一还原一遍O(n)出结果。配合前缀和还能顺带完成区间求和查询。这篇文章把我自己常用的一维差分模板、边界细节、配合作战姿势以及调试时容易踩的坑全部整理一遍。适合刚接触算法的竞赛新手也适合用差分做业务开发、批量数据处理的工程党参考。1. 差分思想与适用场景1.1 从“多次区间修改”到“差异记录”先不着急上代码我们先把差分数组的本质说透。给定原数组 a长度 n构造一个差分数组 diff满足diff[1] a[1] diff[i] a[i] - a[i-1] (i 2)也就是说差分数组存的是原数组每一个位置和前一个位置之间的“差距”而不是直接存原数值。反过来如果有了 diff把 diff 做一遍前缀和就能还原出 aa[i] diff[1] diff[2] ... diff[i]这个互逆关系是整个差分的核心。你可能会问明明直接操作原数组更直观为什么要绕这么一圈原因是区间操作的性质变了。原来“给 a[l..r] 每个元素 v”反映到 diff 上其实只改两个位置位置 l 的差分会增大 v因为它和前面 a[l-1] 的差距变大了位置 r1 的差分会减小 v因为 a[r1] 和 a[r] 的差距变小了如果 r1 在数组范围内。中间那些位置之间的相对关系根本没变所以差分的值完全不需要动。这就把一个长度为区间长度的修改压缩成了两个固定点的修改。所有操作都做完后再做一次前缀和还原原数组得到最终答案。这个方法完美适用于“大量区间操作 最后统一求结果”的场景。1.2 什么信号出现就该想到差分我用差分的判断标准差不多可以总结成下面几条操作全是“区间批量加/减一个常数”操作的次数很大比如 10^5、10^6 量级但最后只查询一次或少数几次不需要随时在线查询中间过程如果是“区间加 区间求和”一般要配合树状数组或线段树但核心更新仍然用差分思路。这里顺手举一个生活化的例子。你在做一个库存管理需求每天有大批订单每个订单对应一批商品在某段时间内增加或减少库存最后月底只核算一次每个商品最终库存。把商品 SKU 当数组下标每个订单就是一次区间加减差分数组记录的是相邻 SKU 之间的库存差值变化最后前缀和归并出每个 SKU 的最终库存。这种场景和数据量下暴力维护原数组肯定是扛不住的。2. 模板实现与边界细节2.1 最标准的一维差分模板C我平时用的模板非常精简核心就三块初始化、区间操作、还原。以 1-based 下标为例#include bits/stdc.h using namespace std; const int N 100005; long long a[N]; // 原数组最终结果存这里 long long diff[N]; // 差分数组 int main() { int n, m; scanf(%d %d, n, m); // 读入初始数组建差分 for (int i 1; i n; i) { scanf(%lld, a[i]); diff[i] a[i]; diff[i 1] - a[i]; } // m 次区间加减操作 while (m--) { int l, r; long long v; scanf(%d %d %lld, l, r, v); diff[l] v; diff[r 1] - v; // 注意是 r1 } // 最后前缀和还原 for (int i 1; i n; i) { a[i] a[i - 1] diff[i]; } // 输出结果 for (int i 1; i n; i) { printf(%lld , a[i]); } return 0; }等一下这个初始化的写法有讲究。很多人习惯先把 diff 设 0然后对每个位置执行“区间加 a[i] 到 a[i]”的操作也就是 diff[i] a[i]; diff[i1] - a[i]; 上面这个写法就是这么来的。你也可以用更直白的公式先读 a再算 diff[i] a[i] - a[i-1]。两种写法都行但上面这种在只有“从 0 空数组逐步建区间值”的场景里更通用比如你打算批量插入初始值。2.2 模板的 JavaScript 版和 Python 版实际项目里经常用 JavaScript 处理批量数据Python 刷题也常见我把两个版本也放出来。JavaScript 版function solve(n, m, initial, operations) { const diff new Array(n 2).fill(0); for (let i 0; i n; i) { diff[i] initial[i]; diff[i 1] - initial[i]; } for (const [l, r, v] of operations) { diff[l] v; diff[r 1] - v; } const res new Array(n); let cur 0; for (let i 0; i n; i) { cur diff[i]; res[i] cur; } return res; }Python 版def apply_diff(n, initial, operations): diff [0] * (n 2) for i in range(n): diff[i] initial[i] diff[i 1] - initial[i] for l, r, v in operations: diff[l] v diff[r 1] - v res [] cur 0 for i in range(n): cur diff[i] res.append(cur) return res核心思路完全一致都是“建差分数组、区间两端修改、前缀和还原”三步。用 0-based 的时候注意区间 [l, r] 的收尾位置是 r1如果 r 是索引下标那么把 v 减到 diff[r 1] 上数组长度记得多开一位。2.3 边界条件和数据范围的计算验证差分模板看起来三行最容易翻车的就是边界。我列几个实际操作时百分百会碰到的细节数组越界diff[r1] 当 r n 时会越界。所以数组开 n2 是底线不是 n。这是个很蠢但很常见的段错误来源。数据类型区间加的值 v 和最终累加结果都可能超过 int 上限。比如 10^5 次操作每次加 10^5最终值可能到 10^10。我统一用 long longJava 用 long别为省内存用 int 然后 Wa。下标从 1 还是从 0如果是 1-based区间是 [l, r] 就是 diff[l]v, diff[r1]-v如果是 0-based区间是 [l, r]也就是 diff[l]v, diff[r1]-v两个表述长得一样但 r 的含义差一位做题前先明确输入给的是闭区间还是开区间、索引从几开始。还原顺序必须等所有区间操作都完成后再统一前缀和。千万不能“做一个操作就还原一次”那样差分就白建了复杂度直接打回原形。举个例子验证一下。假设初始数组 a [1, 2, 3, 4, 5]建差分 diff [1, 1, 1, 1, 1]。执行操作把 [2, 4] 加上 10则 diff[2] 10 - 11diff[5] - 10 - -9。差分数组变为 [1, 11, 1, 1, -9]。前缀和还原1, 12, 13, 14, 5。原数组 [1, 2, 3, 4, 5]给下标 2、3、41-based加 10得到 [1, 12, 13, 14, 5]完全一致。这个手算过程我建议初学者走一遍对理解 diff 里每个位置值的意义非常有帮助。3. 高频变形与配合作战3.1 差分 二分答案把“判断可行性”变成“区间覆盖”单一模板的用途毕竟是有限的差分真正强大的是和各种算法结合。最常见的一个组合是“二分答案 差分验证”尤其见于各种分配类问题。举一个非常典型的场景有一排连续资源位编号 1 到 n有 m 个操作每个操作要求把区间 [l, r] 的资源使用量增加 v。问最多能执行多少个操作而不至于让任意位置的资源使用量超过上限 cap。直接枚举前 k 个操作再暴力判断是否超限复杂度 O(nk)不可行。但用二分 差分就很利索bool check(int k, long long cap) { memset(diff, 0, sizeof(diff)); for (int i 1; i k; i) { diff[op[i].l] op[i].v; diff[op[i].r 1] - op[i].v; } long long cur 0; for (int i 1; i n; i) { cur diff[i]; if (cur cap) return false; } return true; }每次 check 只需要 O(n) 时间配合二分 O(log m) 轮总复杂度 O(n log m)比暴力不知道高到哪里去了。这类题目的命名有很多变体但核心判定逻辑永远是“前 k 次操作之后是否有位置超限”正好是差分最擅长的区间覆盖检查。这种“先二分尝试后差分快速判定”的思路本质上是用空间换时间的经典套路。实际写的时候我最想提醒的一点是check 函数里一定要记得把 diff 数组清零。因为每一轮二分都要重新构建一次差分不清零的话上一次的操作会在这一次里残留结果直接出错。3.2 差分 树状数组 / 线段树区间更新加区间查询差分只能解决“最后统一查询”的问题如果过程中需要频繁查询某个位置的当前值就不能再等比到结尾了。这时差分通常和服务数据结构配合。这里有个经典结论如果需要“区间加 单点查询”可以直接用树状数组维护差分数组。单点查询就是前缀和区间修改就是两次单点更新非常自然。如果需要“区间加 区间求和”就要用两个树状数组或者带懒标记的线段树来维护差分。推导过程是这样的用 diff 的前缀和表示原数组 a[i]那么区间 [1, x] 的和可以这样化简sum(1, x) sum_{i1}^{x} a[i] sum_{i1}^{x} (i 从 1 到 i 的 diff 前缀和) sum_{i1}^{x} (x - i 1) * diff[i] (x 1) * sum(diff[i]) - sum(i * diff[i])所以维护两个树状数组一个存 diff[i]一个存 i*diff[i]就能求出任意前缀和进而得到任意区间和。我在业务代码里也用过这个思路处理日志增量统计一批批次地给某段时间的计数加值同时又想随时查任意时间段的总计数用这个组合就非常合适。说起来差分配合线段树比配合树状数组要笨重一点但如果本来就有现成的线段树支持区间修改那直接线段树 懒标记也行差分并不是必须的。差分的价值在于轻量不需要建树不需要 pushdown纯数组就能跑。3.3 二维差分和树上差分一维模板的延伸一维差分学会后二维差分基本是同一套逻辑的拓展。给一个 n*m 的矩阵要做若干次“子矩阵统一加 v”的操作暴力更新同样不可行。二维差分的更新是diff[x1][y1] v; diff[x2 1][y1] - v; diff[x1][y2 1] - v; diff[x2 1][y2 1] v;四个点的修改等价于把整个子矩阵的范围影响标记在差分矩阵的四个角上。最后做两遍前缀和先按行再按列或者直接用二维前缀和公式还原原矩阵。写的时候容易漏掉“右下角 v”那一步这也是二维差分最常见的 bug。树上差分则是把树上的路径修改变成点上的差分标记。设节点 u 到 v 的路径上每条边都加 v则可以用 diff[u] v、diff[v] v、diff[LCA(u,v)] - 2*v 的标记方式最后 DFS 自底向上累加得到每条边的最终值。这里 LCA 的预处理和维护是另一套东西了但底层“把路径修改转成点标记”的思路和差分一模一样。我提这两个延伸是想说一维差分不仅仅是“一个模板”它是一整套“把区间/路径操作转化成端点标记”的思想。贯通这条主线以后二维差分和树上差分就只是套模板时多几个端点而已不再是什么神秘的东西。4. 常见问题与调试技巧实录4.1 本地样例过了提交却 Wrong Answer怎么排查这个可能是使用差分模板最让人头疼的地方。样例通常给得很温柔一跑就过提交上去却一片红。我踩过的坑大致有这么几类按概率排序类型溢出。数组元素、操作值、累加结果全用 long long但输入没有按 long long 读。尤其是 C 里用 int 读入后赋值给 long long中间就已经溢出了。diff 数组没清零。多组测试数据之间如果忘记初始化上一组的残留值会污染下一组结果。我的习惯是每个测试用例都用memset(diff, 0, sizeof(diff))或者 vector 重新分配。下标理解不一致。输入给的是 0-based 区间你却按 1-based 处理或者题目说“包含端点”模棱两可地处理成半开区间。边界位置搞错。r1 减 v 的 r 是最后一个被修改的位置不是区间长度也不是 r-1。输出格式问题。多个空格、结尾换行、浮点数精度这是另一类 LeetCode 和 OJ 都常见的幺蛾子。排查的时候我的建议是构造一个暴力计数器来对拍。写一个最笨的 O(nm) 版本随机生成 n、m、l、r、v跑 100 组小数据逐位比较差分模板和暴力模板的结果。在哪一位第一个不一致基本就能定位是边界还是类型问题。这个对拍思路非常土但比人眼盯代码有效率得多尤其是数组下标这种肉眼很难看出来的错误。4.2 多组数据的“一次性还原”陷阱再次强调一个容易犯迷糊的点差分数组不是最终结果是“变化量”的载体。只有等所有区间操作都完成前缀和才代表最终状态。有一种误用是每次区间操作之后都执行一次完整的还原把结果存到另一个数组然后下一次操作又基于还原数组重建差分。这样做完全失去了差分的优势复杂度退化成 O(nm)没有任何意义。如果你的代码里出现了“操作一次、还原一次”这种结构十有八九是思路偏了。反过来有些场景确实要求中途查询答案这时就不该再只用裸差分而应当搭配树状数组。我把这个选择画成一个简单的判断标准不用纠结业务细节就看题目要求场景正确的工具只做区间加最后输出一次性全数组结果裸差分区间加 随时单点查询树状数组维护差分区间加 随时区间求和双树状数组或线段树 懒标记二维矩阵区间加最后查结果二维差分树上路径加最后统计边/点权树上差分这张表是我自己现在做题时的快速索引。很多人遇到“区间加 区间求和”就想着线段树没错但如果只是单点查询或者一次性输出线段树就是杀鸡用牛刀差分更省事。4.3 关于初始化那一步我个人的建议最后单独聊聊模板开头那几行初始化。有些人的模板是这么写的for (int i 1; i n; i) { diff[i] a[i] - a[i-1]; }这样当然没问题。但我个人更喜欢用“区间加”的视角来做初始化也就是对每个位置 i 执行一次 [i, i] 加 a[i] 的操作for (int i 1; i n; i) { diff[i] a[i]; diff[i 1] - a[i]; }这样做的好处是初始化逻辑和后续区间操作完全统一可以减少记忆负担。尤其是当你用同一个函数处理“初始数据和后续追加操作”时这个写法改组装的成本最低。代价就是多几次赋值操作但现代机器上完全感觉不到。如果使用这种写法记得 diff 数组要先清零否则第一次累加时会把残留的垃圾值也算进去。我在本地环境里吃过这个亏静态数组初始全 0没问题但换到某些在线环境时局部数组没初始化就出乱子。所以建模板时diff 数组建议统一long long diff[N] {0}或者vectorlong long diff(n2, 0)。4.4 调试时的一个实用技巧打印差分数组很多初学者写完模板跑出错误结果后习惯直接打印原数组然后对着结果发呆。我的经验是先把差分数组打出来看看。差分数组非常有规律。如果只有少数几次区间操作diff 数组应该只在操作起点和终点1的位置有非零值其他位置都是 0。一旦发现 diff 中间出现一堆奇怪的非零值说明要么是区间更新的 l、r 写错要么是还原时机不对。这个特征非常明显比通过结果反推原因快得多。再分享一个小习惯把题目样例用手算一遍然后用printf把每次操作后的 diff 数组打出来对比。我在人工验证模板时就会拿“a[1,2,3,4,5], 对[2,4]加10”这种小样例走一遍确认 diff 变成 [1,11,1,1,-9]再前缀和还原得到 [1,12,13,14,5]全程一目了然。这套核对流程用熟了做算法题时效率能提升不少。5. 最后再分享一点工程实操心得很多人觉得算法模板只在刷题才有用其实工作里更能体会到差分的好处。有一回我在做批量报表统计数据库里有几十万条记录每条记录表示“某个用户在某个时间段内增加了多少访问量”最后要汇总出每个小时的总访问量曲线。最直接的做法是对每条记录遍历覆盖的小时区间累加几十万条记录乘以几十个小时每次跑批要几分钟慢得让人抓狂。后来我换成差分思路时间轴作为数组每条记录就是一次区间加把所有记录映射到 diff 数组的两端操作最后一遍前缀和就出结果跑批时间从几分钟降到了几百毫秒。这种“把逐条区间更新改成两端点标记再统一累加”的思维模式不局限于算法题里的数组下标。所有“对某段连续范围做批量影响最终需要看聚合结果”的场景都可以往差分的框架上靠。日常开发里的排班统计、库存流水、带宽配额、日志聚合几乎都能找到差分的身影。我个人在实际踩坑后的体会是差分算法最玄妙的不是那三行代码而是你能不能识别出哪些问题本质上属于“区间批量修改 最终聚合查询”。这个识别能力一旦建立一维差分模板就是你工具箱里最顺手的一把螺丝刀——轻巧、快速、几乎没有多余开销。把本文的模板背下来再把边界细节和排错思路记牢无论是竞赛里碰到区间操作题还是工程中碰到批量统计需求基本都能有底地完事。
