一维差分数组算法模板：从区间加原理到边界避坑与二维扩展-北京尧图网络

一维差分算法模板这个关键词我估计很多刷题人都不是第一次见。我当年第一次遇到它是在一道“区间加”的题上卡了整整一下午数组长度十万操作次数十万老老实实写了两层循环样例全对一提交就是超时。后来搞懂差分数组才发现这个让我怀疑人生的题正解只需要十几行代码核心思想一句话就能讲完——把“修改一段连续区间”变成“修改两个端点”。这篇文章就把一维差分从原理到模板、从裸题到变种、从边界坑到二维扩展一次讲清楚让你以后遇到“区间加、最后统一输出”的题目不是背模板而是真正能自己把代码推出来。1. 先看清问题本质区间加为什么会把暴力写法拖垮在做差分之前得先理解自己面对的到底是什么问题。所谓“区间加”就是给你一个长度为 n 的数组 a然后给 m 次操作每次给出三个数 l、r、v表示把 a[l] 到 a[r] 之间的所有元素都加上 v做完所有操作后输出整个数组。这类题在竞赛、面试题和日常业务里都很常见。比如一个简单的库存系统某批商品在某段时间内每天补货 v 件你在最后只需要知道每天的总库存又比如统计一个轨迹经过每个点的次数轨迹每次都是一段连续区间。问题听起来平平无奇但一上数据规模事情就不一样了。1.1 两层循环的时间复杂度比你想象的还要可怕最直觉的写法当然是两层循环for (int op 0; op m; op) { for (int i l; i r; i) { a[i] v; } }假设 n m 100000每次实际操作区间都取最坏的 [1, n]内层循环跑 n 次外层循环跑 m 次总共是 10^10 次加法。这个数字什么概念普通评测机一秒大概能执行 10^8 到 10^9 次简单运算10^10 次意味着几十秒起步超时是必然的。有人会下意识想到前缀和。但前缀和只能优化“区间求和查询”却优化不了“区间修改”。因为每次修改之后前缀和数组里的信息就整体失效了必须重新构建一次 O(n) 的前缀和最后还是 O(n×m)。问题的核心在于区间修改和数组还原这两件事之间横着一个“数据规模”的鸿沟。1.2 换个角度看数组与其记每块砖的高度不如记相邻砖的高度差先想象一排砖头从左到右的高度分别是 a[1]、a[2]、……、a[n]。现在要求把第 l 块到第 r 块砖整体垫高一个固定值 v。如果你站在远处观察这一排砖的“轮廓”会发现一件很妙的事虽然中间每一块砖都变了但相邻两块砖之间的高度差绝大多数位置根本没有变化。真正变化的位置只有两个第 l 块砖和它左侧砖块的高度差变了 v因为左边那块没动、右边这块高了第 r 块砖和它右侧砖块的高度差变了 -v因为右边那块没动、左边这块高了。这个观察就是差分数组的全部秘密。我们定义一个数组 diffdiff[i] a[i] - a[i - 1]其中约定 a[0] 0。这个 diff 就叫做原数组 a 的差分数组。只要知道 diff[1] 到 diff[n]就能通过前缀和把 a 还原出来a[i] diff[1] diff[2] ... diff[i]再看区间加 [l, r] 整体加 v在差分数组上会变成什么只有两处改动diff[l] 增加 vdiff[r 1] 减少 v其他位置一律不动。为什么内部不动因为区间内部相邻两个元素的差值没有变化只有区间左边界处和第 l 个元素与前一个元素的差变了右边界处第 r 个元素与后一个元素的差变了。把这个结论看懂后面所有模板代码都只是这个思路的落地而已。暴力写法和差分的复杂度差异可以这样对比环节暴力双层循环差分数组构建差分数组不需要O(n)单次区间修改O(r - l 1)O(1)最终还原数组直接输出O(n) 一次前缀和总复杂度O(n × m)O(n m)明白这一点再看模板就一点都不会觉得玄乎了。2. 一维差分数组的构造与标准模板代码很多教程一上来就甩一段模板但没告诉你模板是怎么组合出来的。实际上差分数组的标准流程就三步构造差分、执行区间修改、前缀和还原。三步分得越清楚越不容易写错。下面是我一直用的 C 模板面向 1-based 数组下标这也是竞赛和多数题解的主流写法#include bits/stdc.h using namespace std; typedef long long ll; const int N 100005; ll a[N], diff[N]; // 区间 [l, r] 整体加 v void add(int l, int r, ll v) { diff[l] v; diff[r 1] - v; } int main() { int n, m; cin n m; for (int i 1; i n; i) { cin a[i]; diff[i] a[i] - a[i - 1]; // 第 1 步构造差分数组 } while (m--) { int l, r; ll v; cin l r v; add(l, r, v); // 第 2 步区间修改只动两个端点 } for (int i 1; i n; i) { diff[i] diff[i - 1]; // 第 3 步前缀和还原 a[i] diff[i]; } for (int i 1; i n; i) { cout a[i] \n[i n]; } return 0; }Python 版本同样常用import sys input sys.stdin.readline n, m map(int, input().split()) a [0] list(map(int, input().split())) diff [0] * (n 2) # 第 1 步构造差分数组 for i in range(1, n 1): diff[i] a[i] - a[i - 1] # 第 2 步区间修改 for _ in range(m): l, r, v map(int, input().split()) diff[l] v diff[r 1] - v # 第 3 步前缀和还原 for i in range(1, n 1): diff[i] diff[i - 1] print( .join(str(diff[i]) for i in range(1, n 1)))2.1 构造差分数组的两种姿势推导法和插入法上面模板用的是推导法直接套定义diff[i] a[i] - a[i - 1];还有一种“插入法”实际调试时更顺手。它的思路是把原数组 a 看成“从全 0 数组经过 n 次单点区间加得到的结果”。也就是说对每个位置 i 执行一次 add(i, i, a[i])for (int i 1; i n; i) { add(i, i, a[i]); }每次 add(i, i, a[i]) 会让 diff[i] a[i]、diff[i1] - a[i]。把所有操作展开后你会发现diff[1] a[1]diff[2] a[2] - a[1]diff[3] a[3] - a[2]和推导法构造出来完全一样。插入法的价值在于当你已经写好了 add 函数就不需要单独记忆构造公式直接调用即可逻辑上是一致的。两种姿势没有优劣怎么顺手怎么来但心里一定要清楚它们等价。2.2 区间加 add(l, r, v) 为什么是两行代码很多人把 add 背下来后第一次写还是会忘记 diff[r 1] - v 这一步。这里用一个最小例子验证。假设初始数组 a [1, 3, 2, 5]差分数组为diff[1] 1 diff[2] 3 - 1 2 diff[3] 2 - 3 -1 diff[4] 5 - 2 3现在执行 add(2, 3, 10)也就是把 a[2] 和 a[3] 都加 10预期结果是 [1, 13, 12, 5]。按模板操作diff[2] 10diff[4] - 10。diff [1, 12, -1, -7]对它做前缀和i1: diff[1] 1 i2: diff[2] 1 12 13 i3: diff[3] 13 (-1) 12 i4: diff[4] 12 (-7) 5结果和预期完全一致。如果你漏了 diff[4] - 10那么前缀和到 a[4] 时会变成 15后面所有元素都会多出 10这就是“只改一头”的错误后果。2.3 从 diff 还原 a一次原地前缀和还原的代码不要单独新开一个数组。直接在 diff 数组上做一遍前缀和就能得到最终数组省空间也省事for (int i 1; i n; i) { diff[i] diff[i - 1]; }这一步做完后diff[i] 就变成了修改后数组 a[i] 的值。所以模板里才敢把还原后的 diff 直接赋回 a。这个动作的核心是“前缀和”千万别把它和“区间求和”里那个前缀和混为一谈这里它干的是“把差分信息还原成原值”。3. 前缀和与差分互逆关系如何帮你判断题型很多初学者学了差分后容易搞混前缀和和差分到底是不是一回事其实它们是一对互逆操作数组经过差分得到差分数组差分数组经过前缀和还原回原数组。就像“加法”和“减法”互为逆运算一样。3.1 差分可以看作前缀和的“逆运算”举一个简单例子。数组 a [1, 3, 2, 5] 的差分是 diff [1, 2, -1, 3]对 diff 做前缀和得到 [1, 3, 2, 5]正好回到 a。这个性质在脑内建立起来后所有区间修改问题都可以换一个视角你维护的不是值本身而是值的“变化”。但要注意前缀和和差分解决的问题并不对称前缀和适合处理“静态数组的区间和查询”构建一次 O(n)之后每次查询 O(1)差分适合处理“多次区间加、最后统一输出或单点查询”每次修改 O(1)最后 O(n) 还原一次。它们不是替代关系而是互补关系。遇到“区间和查询”首选前缀和遇到“区间修改”看到底是最后统一查询还是在线查询再来决定到底用哪个工具。3.2 判断一道题能不能用差分的三个条件根据我刷题的经验一道题目如果同时满足下面三个条件基本可以直接安排差分数组每次操作都是对一段连续区间加/减同一个常数查询要么是“单点查询”要么是“所有操作结束后统一输出数组”数据规模大到暴力 O(n×m) 不可接受。反过来如果题目要求每次修改后立刻查询区间最大值或者每次修改后立刻查询区间和那差分模板就不能直接套。不是说差分失效而是单纯的差分数组在不做完整前缀和的情况下回答不了在线区间查询。这时需要换工具最常见的是树状数组或线段树。3.3 差分、树状数组、线段树三者怎么选“区间修改区间查询”这个大类里工具选择是个老大难。我给过自己一个速查表分享出来需求推荐方案单次复杂度静态数组区间和查询前缀和预处理 O(n)查询 O(1)区间加最后统一输出差分数组修改 O(1)最后 O(n)区间加在线单点查询树状数组维护差分修改 O(log n)查询 O(log n)区间加在线区间和查询线段树 / 树状数组维护双差分修改 O(log n)查询 O(log n)区间赋值等更复杂的懒操作线段树懒标记O(log n)为什么区间加在线单点查询要用树状数组而不能直接用差分数组因为差分数组本身只存了“相邻差”在没有做完前缀和之前你并不知道某个单点的当前值。每次查询都重新做一遍前缀和又回到了 O(n)。树状数组刚好可以支持动态前缀和所以它能在线回答单点查询。理解这个边界比记住“区间修改用差分”这句话重要得多。4. 三个经典实战场景读懂比背模板更重要模板只是第一关能在一道具体题目里识别出差分才是真正的分水岭。下面用三个经典场景拆开讲难度从直接套用到变形进阶逐个过一遍。4.1 区间加裸题核心模板的直接套用最典型的裸题就是“给定一个数组做 m 次区间加最后输出整个数组”。输入格式都不需要变上面的模板可以直接交。这类题目的价值主要是让你把“构造、修改、还原”三个动作练到条件反射。我通常建议新手在本地手写一遍完整的代码然后加入一小段输出 debug 信息比如打印每次 add 之后的 diff 数组。很多人以为这是浪费时间实际上当你亲眼看到 add(2, 3, 10) 之后 diff 里只有两个位置发生变化时对差分的理解会比背十遍模板都深。4.2 LeetCode 1109 航班预订统计区间从 1 开始反而更顺LeetCode 1109 是一道很经典的差分应用题。题目给若干条预订记录 bookings[i] [first, last, seats]表示从 first 到 last 的航班每个航班都要增加 seats 个座位最后返回 n 个航班的座位数。所有修改先给完最后统一输出天然就是差分数组的菜。因为题目航班编号从 1 开始而答案数组下标从 0 开始很多人会在这里绕晕。用差分时直接保持内部 1-basedclass Solution { public: vectorint corpFlightBookings(vectorvectorint bookings, int n) { vectorlong long diff(n 2, 0); for (auto b : bookings) { int l b[0], r b[1], v b[2]; diff[l] v; diff[r 1] - v; } vectorint ans(n); long long cur 0; for (int i 1; i n; i) { cur diff[i]; ans[i - 1] cur; } return ans; } };这里有个小细节diff 的长度开的是 n 2因为当 r n 时 diff[r 1] 会访问到 diff[n 1]下标必须存在。这也是无数人翻车的地方之一后文会专门展开。4.3 洛谷 P4552 IncDec Sequence差分思维的进阶用法裸题会做之后一定要试一道变种题。洛谷 P4552 是我心中最好的差分思维进阶题。题目大意是给定一个长度为 n 的序列 a每次可以选择一个区间 [l, r]把这个区间里的所有数都加 1或者都减 1。要求用最少的操作次数让整个序列所有数变成一样并且问最终能变成几种不同的值。如果直接想原数组非常绕。但转成差分数组后问题立刻变得清晰起来。先把长度为 n 的数组转成 n 1 个差分值b[1] a[1]b[i] a[i] - a[i-1]i 2..nb[n1] -a[n]。“所有数变成一样”等价于让 b[2] 到 b[n] 全部变成 0而 b[1] 和 b[n1] 是什么值不重要。一次区间整体加 1等价于选择差分数组里的两个位置一个 1一个 -1。区间整体减 1 则是反过来。所以问题变成了通过反复把任意两个差分值一个 1、一个 -1让中间 b[2]..b[n] 全部归零。这里可以贪心统计 b[2]..b[n] 中所有正数的和 pos以及所有负数绝对值的和 neg。每次操作可以让一个正数和一个负数同时抵消逼近 0剩余的绝对值只能和 b[1] 或 b[n1] 互相抵消。因此最少操作次数 max(pos, neg)最终能得到的种类数 abs(pos - neg) 1。核心代码#include bits/stdc.h using namespace std; typedef long long ll; int main() { int n; cin n; vectorll a(n 1), b(n 2); for (int i 1; i n; i) { cin a[i]; b[i] a[i] - a[i - 1]; } b[n 1] -a[n]; ll pos 0, neg 0; for (int i 2; i n; i) { if (b[i] 0) pos b[i]; else neg -b[i]; } cout max(pos, neg) \n; cout abs(pos - neg) 1 \n; return 0; }这道题妙就妙在它把“区间操作”降维成了“差分数组两大阵营的配对抵消”做完之后你会对差分的作用有一种全新的感觉原来所谓区间操作本质上就是边界变化的传递。5. 实战里最容易踩的坑边界、溢出与更新顺序代码本身不难但差分数组在实战中的翻车点非常固定。这里把我踩过和看别人踩过的坑集中梳理一遍每一条都很具体。5.1 下标从 0 开始还是从 1 开始翻译要统一很多题目给的下标是 0-based而我的模板默认 1-based。转换时最稳的做法是读到一个 0-based 区间 [l, r] 时立刻转换成 add(l 1, r 1, v)。不要试图在模板里混合使用两种下标规则否则很容易出现“左边界加了 1、右边界没加 1”的错位。我见过一个典型错误题目 0-based有人想省事直接写 add(l, r, v)结果发现最后数组从第 l 个位置开始的值全都不对debug 半小时才发现是下标偏移问题。统一规则是编码的第一优先级。5.2 diff 数组为什么至少开 n 2这是新人踩得最狠的坑。区间加要操作 diff[r 1]当 r n 时下标就是 n 1。如果你只开长度为 n 的数组diff[n 1] 直接越界开 vector 开 n 1 长度时访问 diff[n 1] 也会越界。所以 C 风格数组建议 const int N n 5 或者直接静态数组开大一点动态数组就开 n 2。这样即使 r 取到 ndiff[n 1] 也有安全空间可以写。Python 里的列表同理初始化为 [0] * (n 2) 才稳妥。越界不是每次都会崩溃C 里未定义行为可能刚好没崩但结果完全是随机的。你可能会在本地跑得好好的交上去却莫名 WA这类问题排查起来非常耗时。5.3 用 long long 而不是 int差分数组里累积的值远不是表面看起来那么简单。假设 n 200000m 200000每次操作都是区间 [1, n] 加 10^9那么最终每个元素会被加上 2 × 10^14这个数量级远超 int 的约 21 亿上限。所以只要数据范围超过 10^5 且操作值可能到 10^9就一律用 long long。我的模板里 add 函数的参数 v 和数组 diff、a 都用了 long long不是小题大做而是这段代码在很多场景下真的会出锅。Python 没有溢出问题但在 C 里 int 溢出往往是隐蔽的有时候负溢出刚好能在小数据下“巧合”地得到正确结果一上大数据就全盘崩溃。5.4 还原后再 add 或者忘了还原的经典翻车差分的生命周期是固定的先构造再集中修改最后前缀和还原。这三步不能随意打乱否则就会错得莫名其妙。错误写法一忘了还原直接输出 a。while (m--) { int l, r, v; cin l r v; add(l, r, v); } // 忘了一步diff 前缀和还原后再赋值给 a for (int i 1; i n; i) { cout a[i] ; // 输出的是原数组 }错误写法二先做了前缀和还原之后又继续 add。第 3 步完成之后diff 数组里存的已经是“还原后的原数组值”不再是严格意义上的差分数组了。此时再执行 diff[l] v、diff[r1] - v再跑一轮前缀和得到的结果和真正想要的结果完全不是一回事。我的经验是把这三步当成三个阶段代码注释写清楚。凡是看到自己反复修改同一段逻辑却搞不清哪一步是当前状态时大概率就是阶段混淆了。6. 一维差分的延伸二维差分、离散化与树上差分一维差分学会之后最重要的是看出它的本质是“范围修改转变成端点标记”。一旦想通这一点二维差分、离散化差分甚至树上差分都不难理解。6.1 二维差分的区域加模板先看二维。矩阵有 n 行 m 列现在要把子矩阵 (x1, y1) 到 (x2, y2) 这个矩形范围内的所有元素都加 v最后输出完整矩阵。暴力是 O(矩形面积)一维差分的思路到二维依然有效但端点从一个变成四个。模板公式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; }直觉和二维前缀和完全一致左上角加 v 影响整个右下区域右边和下边减去 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]; } }LeetCode 2536 的“子矩阵元素加 1”就是二维差分的直接应用。你可能一开始背不住这四个端点但只要画一遍容斥图很快就能自己推出来。6.2 坐标范围太大怎么办离散化差分有时候区间端点可能到 10^9比如给若干条线段 [l, r]每条线段覆盖值 1最后统计覆盖次数最多的区域。如果直接开长度为 10^9 的数组内存直接爆炸。这时可以把所有出现的坐标收集起来排序后去重然后只对“相邻两个坐标点之间的这一段”开差分数组。区间 [l, r] 的加操作映射到离散化后的坐标段下标上仍然只是两个端点的修改。这就是“离散化差分”配合扫描线可以解决很多区域覆盖类问题。关于离散化有一个隐藏细节要搞清楚 diff 数组里的每个桶究竟代表“一个点”还是“相邻两点之间的一段”。如果题意统计的是点覆盖次数用点坐标做桶如果统计的是区间长度和用相邻坐标段做桶。搞混这个是离散化差分的头号错误来源。6.3 树上差分同一个思想换了个载体树上差分是竞赛进阶里一个独立的小专题核心思想完全一致把“路径上所有点权加 v”或者“所有边权加 v”这类操作转换成树上少数几个端点的标记。比如点差分的经典写法是 u 和 v 打上 v 标记lca 和 lca 的父节点打上 -v 标记最后 dfs 一次汇总。树上差分虽然载体从数组变成了树但底层逻辑仍然是“范围操作等于端点修改”。先在一维把这句话吃透将来接树上问题时就不会觉得突兀。最后聊几句个人感受如果你刚开始学算法模板我的建议是别急着背。一维差分的全部内容其实就一句话区间操作只在端点上留下痕迹最后用前缀和把这些痕迹传播开。我第一次把这句话彻底想通花了整整一个下午之后二维差分、树上差分、扫描线里的差分我都是靠自己推出来的没有再死记硬背过公式。练习路径上我推荐先手写一遍裸题的完整代码然后做 LeetCode 1109 验证 0-based 和 1-based 的转换最后用洛谷 P4552 体会一次“区间操作退化为端点配对”的高级用法。每一次都把 long long、n 2 的空间、最后的还原条理写清楚形成肌肉记忆以后你会感激自己在这上面多花的时间。

一维差分数组算法模板：从区间加原理到边界避坑与二维扩展

相关推荐

Python驱动睿尔曼仿人机械臂：医疗工作站抓取与视觉引导实战

agedu磁盘分析工具实战：快照索引轻松揪出Linux大文件与空间占用

Hive查询重写优化实战：从慢SQL到19分钟收工的改造路径

更多资讯

Windows软件狗驱动安装失败原因与兼容性解决方案

杰理AC79 Wi-Fi编程模型：事件驱动与分层回调实战解析

用Harness工作流编排Agent，Token成本直降50%

Agent-Reach：多Agent协作的触达层设计与部署实战

C#位运算精讲：按位与()和按位或(|)的实战指南

BeyondCompare x64中文版：文件比较、文件夹同步与Git集成

今日更新

Agent Skills 完全指南：原理、写法、安装与实战避坑

Agent Skills 实战：从 Genkit 定义到 GKE 部署与排查

Agent Skills 实战：从设计到调试的完整指南

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？