如果你刷过 LeetCode 或者打过蓝桥杯、多校赛大概率遇到过这类题给一个数组m 次区间加法最后把整个数组输出。暴力 for 循环当然能写但 n 和 m 都到 (10^5) 级别时(O(n \times m)) 直接把一个好好的思路卡到超时。我第一次在线比赛被这种题卡住的时候还以为是语言或编译器问题后来才明白这种“区间批量修改 最后统一查询”的场景就该让差分数组上场。这篇文章我从一维开始逐步推到二维、三维差分数组把原理、图解、模板和例题拆开讲清楚。不是只给结论而是把“为什么 l 处c、r1 处−c”“为什么二维要动四个点、三维要动八个点”这种底层逻辑讲透。无论你是刚开始刷题的新手还是想系统梳理差分家族的竞赛党都可以照着文章自己手撕一遍。1. 暴力 for 循环撑不住的时候差分数组就该上场了1.1 暴力区间修改的复杂度灾难先看一个最朴素的问题模型。有一个长度为 (n) 的数组 (a[1..n])初始全是 0现在给你 (m) 次操作每次都把区间 ([l, r]) 内的所有元素加上 (c)最后输出每个位置的值。最直觉的写法是这样for (int i 1; i m; i) { int l, r, c; cin l r c; for (int j l; j r; j) { a[j] c; } }逻辑完全没错但复杂度是实打实的 (O(n \times m))。假设 (n 10^5)、(m 10^5)区间平均长度是 (5 \times 10^4)总操作次数大约 (5 \times 10^9)在一秒左右的时限里根本跑不完。很多新手会想“我优化一下循环、开 O2、用快读是不是就行了”实际上这条路走不通。因为问题本质不是常数大而是算法复杂度太高。我们真正需要的是不要每次操作都真的去改数组里的每个元素而是把操作以一种更紧凑的形式“记”下来最后一次性还原。1.2 差分是前缀和的逆运算要理解差分先回忆前缀和。前缀和是这样定义的[ pre[i] \sum_{j1}^{i} a[j] ]而差分数组 (d[i]) 的定义则是[ d[1] a[1], \quad d[i] a[i] - a[i-1] \quad (i \ge 2) ]如果对差分数组 (d) 从头做一次前缀和你会发现它精确地还原出原数组 (a)反过来对原数组 (a) 做差分也能得到 (d)。它们是一对互逆操作类似于积分和微分的关系。这个关系有什么用关键在这里前缀和擅长把“单点值”变成“区间累计值”差分则擅长把“区间操作”变成“单点操作”。当我们想给区间内所有元素都加 (c) 时我们其实不需要逐个修改元素只需要修改区间边界处的“差分值”让它在做前缀和的过程中自然传播到整个区间。1.3 差分数组能干什么、不能干什么我见过不少人学完差分之后什么题都往上套结果用错场景反过来说“差分没用”。其实差分有非常清晰的使用边界。差分数组适合的场景是多次区间修改最后一次性查询全部结果多次区间修改之后有大量单点查询并且这里查询是离线完成的配合二分答案把“检查某轮操作后的状态”变成高效的批量重放。差分数组不适合的场景是需要在线边修改、边查询某个区间的和需要每次修改后立刻知道某个位置的新值且修改和查询交替出现。如果遇到后面这两种情况通常应该考虑树状数组或者线段树。这不是差分不好而是工具没选对。把这个边界搞清楚后面用起来才不会跑偏。2. 一维差分l 处 c、r1 处 −c一次前缀和还原真相2.1 一维差分数组的构造与物理意义假设原数组是 (a[1..n])对应的差分数组是 (d[1..n])那么[ d[1] a[1], \quad d[i] a[i] - a[i-1] \quad (i 2..n) ]怎么理解这个 (d[i])我自己的习惯是把数组想象成一列台阶的高度。原数组记录的是每级台阶的绝对高度差分数组记录的是每级台阶相对上一级的高度差。从第 1 级开始把所有高度差累加起来就能算出任意一级台阶的绝对高度。所以对 (d) 做前缀和得到 (a)这个操作本质上就是“从高度差还原高度”[ a[i] d[1] d[2] \cdots d[i] ]构造差分数组有两种套路。第一种是直接按定义算for (int i 1; i n; i) { diff[i] a[i] - a[i - 1]; }第二种是用一个统一的add操作把每个位置 (i) 的单点值看作一次区间 ([i, i]) 的加法。这种方法在二维、三维差分里特别香因为代码风格完全一致不易记混。后面我会主要用第二种。2.2 为什么区间 ([l, r]) 加 c 只需要动两个端点这是整个差分数组最核心的一个问题。先说结论void add(int l, int r, int c) { diff[l] c; diff[r 1] - c; }为什么区间内所有元素都加 (c)却只更新两个位置原因是差分数组保存的是“相邻元素之间的差值”。区间内部相邻元素的差在批量加同一个数时完全不变真正变化的只有两处边界在 (l) 处左边的值和 (a[l]) 之间多出了 (c) 的差值在 (r 1) 处(a[r]) 和右邻居之间多出了 (-c) 的差值。更严谨一点对 (diff) 做前缀和还原时[ pre[i] \sum_{j1}^{i} diff[j] ]在 (i l) 时前缀和没受到任何影响当 (i) 从 (l) 开始多出来的 (c) 被计入前缀和直到 (i \ge r 1)又遇到 (-c) 被抵消。于是只有 ([l, r]) 这段前缀和结果整体多了 (c)完美对应区间加法。举个具体例子。数组长度 8区间 ([2, 5]) 加 3。初始化所有值为 0差分数组一开始也是 0执行add(2, 5, 3)后下标: 1 2 3 4 5 6 7 8 diff: 0 3 0 0 0 -3 0 0 前缀和: 0 3 3 3 3 0 0 0看到没有从下标 2 到 5前缀和正好都是 3。这就是差分数组区间修改的全部秘密。2.3 图解标记点如何扩散成整个区间用一张 ASCII 示意图来看diff数组只在两个位置有值但前缀和的“扫描”过程让增量从 (l) 开始延续到 (r1) 处停止l2 r16 ↓ ↓ index: 1 2 3 4 5 6 7 8 diff: 0 3 0 0 0 -3 0 0 └─────────────────┘ 前缀和一直带着 3你把这个过程理解为“做标记”在起点放一个正号在终点后一格放一个负号之后从前到后扫一遍正负号自然切出我们想要的区间。2.4 一维差分模板C / Python我平时写一维差分最常用这套 C 模板#include bits/stdc.h using namespace std; const int N 100010; long long diff[N]; // 用 long long防止多次累加溢出 void add(int l, int r, long long c) { diff[l] c; diff[r 1] - c; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; // 读入原数组并构造差分数组每个单点值看作区间 [i, i] 加一次 for (int i 1; i n; i) { int x; cin x; add(i, i, x); } // m 次区间修改 while (m--) { int l, r; long long c; cin l r c; add(l, r, c); } // 一次前缀和还原 for (int i 1; i n; i) { diff[i] diff[i - 1]; cout diff[i] ; } return 0; }Python 版本同样简洁n, m map(int, input().split()) diff [0] * (n 2) # 多开一位防止 r1 越界 def add(l, r, c): diff[l] c diff[r 1] - c a list(map(int, input().split())) for i, x in enumerate(a, start1): add(i, i, x) for _ in range(m): l, r, c map(int, input().split()) add(l, r, c) for i in range(1, n 1): diff[i] diff[i - 1] print(diff[i], end )有一个细节要强调diff数组必须开到n 2。因为当r n时diff[r 1]也就是diff[n 1]会被更新虽然它不参与最后的前缀和输出但访问这个索引是合法的。2.5 例题实战LeetCode 1109 航班预订统计题目是这样的有 (n) 个航班编号从 1 到 (n)。给定一个bookings数组每个元素[first, last, seats]表示从first到last每个航班都预订了seats个座位。最后返回长度为 (n) 的数组每个位置是这个航班的预订总数。这不就是一个裸的一维差分题吗把每个booking看成一次区间加法class Solution { public: vectorint corpFlightBookings(vectorvectorint bookings, int n) { vectorint diff(n 2, 0); for (auto b : bookings) { int l b[0], r b[1], seats b[2]; diff[l] seats; diff[r 1] - seats; } vectorint ans(n); int cur 0; for (int i 1; i n; i) { cur diff[i]; ans[i - 1] cur; // 题目是 1-based输出要转回 0-based } return ans; } };这里最容易踩的坑是下标转换bookings里的航班编号是 1 开始的但答案数组是 0 开始的。我在第一次写时忘了把ans[i - 1]对应好结果整体错位。解决办法很简单还原时用 1 到 n 遍历赋值给ans[i - 1]。2.6 一维差分最容易踩的坑第一r 1越界。很多人把diff开成n大小当r n时直接访问diff[n 1]要么越界要么覆盖到其他变量。稳妥做法是开n 2并且在写模板时养成习惯。第二累加溢出。区间可能被操作很多次int不够用。我一律用long long存差分值尤其看到题目数据范围到 (10^9) 时更不能用int硬抗。第三搞混“修改前构造差分”和“修改后还原”的顺序。正确流程是先通过add(i, i, a[i])把初始数组的差分数组构造出来再执行所有区间修改最后才做前缀和还原。如果一边修改一边还原后续修改的标记就会污染已经还原出的值。3. 二维差分四个角标背后的容斥原理3.1 从二维前缀和推导二维差分一维搞明白之后二维的本质就是一维在高维上的推广。先回忆二维前缀和[ sum[i][j] a[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] ]公式里的 (- sum[i-1][j-1]) 是因为sum[i-1][j]和sum[i][j-1]都包含了sum[i-1][j-1]这块区域多算了一次所以要减去。那么二维差分怎么定义把上面这个公式反解用sum表示a得到[ a[i][j] sum[i][j] - sum[i-1][j] - sum[i][j-1] sum[i-1][j-1] ]如果我们的差分数组叫diff构造时其实是在对原数组做这个“逆运算”。不过在实际代码里更常用的做法依然是add(i, j, i, j, a[i][j])把每个单点看成一次 (1 \times 1) 子矩阵的区间加。3.2 子矩阵加 c 的四个角标为什么这样摆现在问题来了如果想给左上角 ((x1, y1))、右下角 ((x2, y2)) 的子矩阵整体加 (c)应该怎么更新差分数组答案void add(int x1, int y1, int x2, int y2, int c) { diff[x1][y1] c; diff[x2 1][y1] - c; diff[x1][y2 1] - c; diff[x2 1][y2 1] c; }很多人看一眼觉得对称就直接背。但必须理解为什么右下角是c。因为差分数组还原时要做二维前缀和某个位置的标记会向右、向下两个方向传播(x1, y1) c让整个右下方向都带上 (c)这范围太大了(x2 1, y1) - c把从 (x21) 行开始的传播拦掉(x1, y2 1) - c把从 (y21) 列开始的传播拦掉但是(x21, y21)这个位置被两个-c都传播到了相当于多减了一次需要补一个c。这个“多减了要补回来”的操作就是二维容斥原理。四个角标正好对应二维前缀和公式里的四项符号也和公式一致、-、-、。3.3 图解四个角标如何在矩阵中传播假设矩阵大小是 (8 \times 8)要给 ((2,2)) 到 ((5,5)) 的子矩阵加 1。四个标记位置分别是y12 y216 ↓ ↓ x12 1 -1 x216 -1 1用 ASCII 示意图表示标记和前缀和的传播效果列: 1 2 3 4 5 6 7 8 行1: . . . . . . . . 行2: . [1] . . . [-1] . . 行3: . . . . . . . . 行4: . . . . . . . . 行5: . . . . . . . . 行6: . [-1] . . . [1] . . 行7: . . . . . . . .做完二维前缀和后从 (2,2) 向右向下扩散的正标记会在 (2,6) 和 (6,2) 被负标记截断然后在 (6,6) 补回来。最终只有 (2,2) 到 (5,5) 这个矩形区域的结果是 1其余都是 0。这也是为什么二维差分比一维多两个标记点因为二维前缀和是向两个方向传播的每一个方向都要“拦”拦完还要处理交叉位置的重叠。3.4 二维差分模板C二维差分代码风格和一维保持统一就非常不容易写错。const int N 1010; long long diff[N][N]; void add(int x1, int y1, int x2, int y2, long long c) { diff[x1][y1] c; diff[x2 1][y1] - c; diff[x1][y2 1] - c; diff[x2 1][y2 1] c; } // 还原对 diff 数组做二维前缀和 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[i][j]最终就变成原数组a[i][j]。这个的过程本身就是在原地做二维前缀和不需要再开一个sum数组。3.5 例题实战洛谷 P3397 地毯题目很好懂在 (n \times n) 的网格上铺 (m) 块地毯每块地毯覆盖左上角 ((x1, y1)) 到右下角 ((x2, y2)) 的区域最后输出每个格子被多少块地毯覆盖。看到“覆盖次数”和“最后统一输出”明显就是二维差分的裸题。每块地毯相当于给一个子矩阵加 1最后做二维前缀和还原。#include bits/stdc.h using namespace std; const int N 1010; int diff[N][N]; void add(int x1, int y1, int x2, int y2) { diff[x1][y1] 1; diff[x2 1][y1] - 1; diff[x1][y2 1] - 1; diff[x2 1][y2 1] 1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; while (m--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; add(x1, y1, x2, y2); } for (int i 1; i n; i) { for (int j 1; j n; j) { diff[i][j] diff[i - 1][j] diff[i][j - 1] - diff[i - 1][j - 1]; cout diff[i][j] ; } cout \n; } return 0; }复杂度是 (O(m n^2))比直接暴力枚举每个地毯覆盖点要快得多。这道题也特别适合用来验证自己对二维差分的理解把样例跑一遍再手工算一次二维前缀和基本就通了。3.6 二维差分的初始化与索引习惯如果你手里不是从 0 开始的差分数组而是已经有一个初始二维矩阵需要先构造差分数组最稳的方法还是统一走addfor (int i 1; i n; i) { for (int j 1; j m; j) { int x; cin x; add(i, j, i, j, x); } }这样做虽然每次add有四次更新但思路一致性极高从一维带到二维、再带到三维都不容易出错。还有两个习惯值得养成。第一坐标一律从 1 开始不要用 0 下标。差分数组在 1-based 下标下的边界判断非常自然x2 1、y2 1就算越界到n 1、m 1也只是落到数组的边界外一格不会误伤有效数据。第二数组维度至少开N 2别开正好的N。我在做洛谷这道题时曾经把diff开成N结果n 1000时访问diff[1001]直接越界报错找了好一会。4. 三维差分八个角标的符号表立体区间修改不再靠枚举4.1 三维前缀和与三维差分的数学对应三维差分在竞赛题里出现频率比一维、二维低但一旦出现基本都是压轴题级别的区分度。它的推导逻辑和二维完全一样只是多了一个维度容斥的项数从 4 变成 8。三维前缀和公式[ \begin{aligned} sum[i][j][k] a[i][j][k] sum[i-1][j][k] sum[i][j-1][k] sum[i][j][k-1] \ - sum[i-1][j-1][k] - sum[i-1][j][k-1] - sum[i][j-1][k-1] \ sum[i-1][j-1][k-1] \end{aligned} ]这个公式的记忆方法一维的项是 2 个二维是 4 个三维是 8 个每多一个维度就多一组“隔着两个维度的项”。符号按包含的维度数决定奇数个减号维度的项为负偶数个为正。三维差分的还原就是对diff数组做一次完整的三维前缀和。由于diff的每个标记会被传播到 (x)、(y)、(z) 三个方向想要描述一个长方体区域的“净增量”必须同时处理所有边界和边界交叉。4.2 八个角标的符号一个表格搞定立体容斥假设要给一个长方体 ((x1, y1, z1)) 到 ((x2, y2, z2)) 内的所有位置加 (c)。和一维两个端点、二维四个角标对应三维需要更新八个角标void add(int x1, int y1, int z1, int x2, int y2, int z2, long long c) { diff[x1][y1][z1] c; diff[x2 1][y1][z1] - c; diff[x1][y2 1][z1] - c; diff[x1][y1][z2 1] - c; diff[x2 1][y2 1][z1] c; diff[x2 1][y1][z2 1] c; diff[x1][y2 1][z2 1] c; diff[x2 1][y2 1][z2 1] - c; }符号规律其实特别好记。记起点是(x1, y1, z1)终点加一后的坐标是(X, Y, Z)其中 (X x21)、(Y y21)、(Z z21)。八个角标每个都是由x1或X、y1或Y、z1或Z组合出来的。符号由“取了多少个终点坐标”决定角标坐标取终点坐标的个数符号(x1, y1, z1)0(X, y1, z1)1-(x1, Y, z1)1-(x1, y1, Z)1-(X, Y, z1)2(X, y1, Z)2(x1, Y, Z)2(X, Y, Z)3-奇数个终点坐标取负号偶数个取正号。这和二维的符号规律完全一致(x1,y1)是 0 个终点正(X,y1)和(x1,Y)是 1 个终点负(X,Y)是 2 个终点正。如果不想背八个坐标可以这样记忆想象一个立方体的八个顶点从起点开始每把一个坐标从x1/y1/z1换成X/Y/Z符号就翻转一次。改动一个坐标变号改动两个坐标又变回来改动三个坐标再变号。我也在底下贴一个我常用来推导的写法先写成三重循环枚举(i,j,k)其中i取x1或Xj取y1或Yk取z1或Z符号是(-1)^(bits)这样永远不会漏。4.3 三维差分还原的三重前缀和和二维一样三维差分做完标记后最后一步是对diff数组做三维前缀和。还原代码看起来长但就是前面公式的直接翻译for (int i 1; i A; i) { for (int j 1; j B; j) { for (int k 1; k C; k) { diff[i][j][k] diff[i - 1][j][k] diff[i][j - 1][k] diff[i][j][k - 1] - diff[i - 1][j - 1][k] - diff[i - 1][j][k - 1] - diff[i][j - 1][k - 1] diff[i - 1][j - 1][k - 1]; } } }这里有一个细节三重循环必须按照从 1 到最大值的递增顺序执行。因为计算diff[i][j][k]时要用到diff[i-1][j][k]、diff[i][j-1][k]等已经更新过的值这些位置在本轮循环之前就已经算好了。如果打乱循环顺序就会用到旧值结果全错。4.4 三维差分的空间开销与优化思路三维差分的最大问题不是原理而是内存。假设长方体尺寸是 (100 \times 100 \times 100)那就是 (10^6) 个格子开long long大约 8 MB完全没问题。但如果是 (500 \times 500 \times 500)就是 (1.25 \times 10^8) 个格子一个long long数组就要 1 GB直接超内存。主流优化有两种。第一种是压维把三维数组映射到一维数组里减少每层数组的额外开销同时利用一维索引做连续内存访问。第二种是如果只需要判断“是否存在某个点被击穿”可以在还原过程中边算边判断不需要把整个还原结果存下来。很多三维差分的题目都需要配二分答案这时可以根据二分范围动态开数组或者复用同一个diff数组。4.5 例题实战蓝桥杯“三体攻击”这道题是我第一次真正感受到三维差分价值的地方。题目大意是有一个 (A \times B \times C) 的立方体每个格子有初始生命值。接下来有 (m) 轮攻击每轮攻击会对方体内某个子长方体造成等量伤害。问第几轮攻击时第一次出现某个格子累计伤害已经超过其生命值也就是被击穿。数据范围不小的前提下逐个格子模拟显然不行。但因为只问“最早第几轮”很自然地想到二分答案二分一个攻击轮数mid把前mid轮攻击全部用三维差分做“子长方体加伤害”对diff做三维前缀和还原扫描所有格子看是否存在某个格子累计伤害不小于生命值存在说明答案在[1, mid]否则答案在(mid, m]。伪代码结构大概是这样bool check(int mid) { memset(diff, 0, sizeof(diff)); for (int i 1; i mid; i) { add(atk[i].x1, atk[i].y1, atk[i].z1, atk[i].x2, atk[i].y2, atk[i].z2, atk[i].dmg); } for (int i 1; i A; i) for (int j 1; j B; j) for (int k 1; k C; k) { // 三维前缀和还原 } for (int i 1; i A; i) for (int j 1; j B; j) for (int k 1; k C; k) if (hp[i][j][k] diff[i][j][k]) return true; return false; }二分次数是 (O(\log m))每次check要重放mid轮攻击并扫描整个立方体总复杂度大约是 (O((m A \times B \times C) \log m))。这种题暴力写不出这种数量级的效率差分数组在这里就是关键先生。4.6 三维差分配二分的几个注意点第一check里每次都要重新初始化diff不要用vector反复 resize性能很差直接用固定数组加memset更稳。第二伤害累加可能超过intdiff和生命值数组都建议用long long。第三二分边界要小心。如果第一轮攻击就击穿答案可能是 1如果最后一轮都没击穿需要额外判断。我习惯把二分的右边界设为m 1检查check(m)都不满足时输出-1或题目要求的特殊值。5. 差分数组模板速查与实战避坑从模板到例题的最后一公里5.1 三个维度的模板速查对照表把一维、二维、三维的关键信息放在一张表里背模板之前先看规律。维度区间修改对象标记点数量符号规律还原复杂度一维区间 ([l, r])2起点 终点后一格 −(O(n))二维子矩阵 ((x1,y1)) 到 ((x2,y2))4左上 右上 −左下 −右下 (O(n \times m))三维子长方体 ((x1,y1,z1)) 到 ((x2,y2,z2))8奇数个终点坐标为 −偶数个为 (O(A \times B \times C))无论几维核心思想都是同一个把对一大片区域的修改转换成对边界几个点的修改最后用一次前缀和把效果扩散回整个区域。5.2 “还原”阶段的更新顺序细节三个维度的还原都是原地做前缀和但这里的顺序细节经常被忽略。一维从头到尾扫二维按行、列依次扫三维按 (i, j, k) 三重递增扫。核心原则是计算当前点的时候所有依赖的“前驱点”都必须已经更新完。写二维还原时很多人会手滑写成diff[i][j] diff[i][j - 1] diff[i - 1][j] - diff[i - 1][j - 1];这其实没问题因为三个前驱点(i, j-1)、(i-1, j)、(i-1, j-1)在递增循环中都已经被处理过。我把这个细节单独拿出来说是因为一旦有三维题目循环顺序错了很难排查甚至样例都能过大点数据就挂。5.3 别把差分数组用错场景差分数组虽然有奇效但它是一个“离线工具”。我见过一些同学拿到“区间加、区间求和”的题想都不想直接差分结果发现算不出在线答案。这里给一个快速判断表需求推荐工具多次区间修改最后统一输出每个点差分数组多次区间修改最终答案靠单点查询差分数组 前缀和需要在线单点更新 区间求和树状数组需要在线区间更新 区间求和线段树 / 带 lazy 标记的树状数组需要在线区间更新 单点查询树状数组差分维护差分数组不是万能的但它的优点是极度简单、常数小、实现快。在离线场景下能用差分解决的问题没必要上更重的数据结构。5.4 我踩过的几个真实坑最后讲几个我自己在实战中踩过的坑希望能帮你少走弯路。第一个是数组开小。一维时diff[r 1]需要n 1二维时diff[x2 1][y2 1]需要n 2行和列三维更是每个维度都要多留一位。我现在写数组直接开N 5宁可多一点也不要越界。第二个是int溢出。洛谷 P3397 那种只加 1 的题目int勉强够用但如果是多轮区间加、或者像“三体攻击”这种要累加伤害的题diff随时可能爆。我现在一律用long long不会错。第三个是二维和三维add的符号写反。尤其是三维八个角标很容易漏或者多写。我的习惯是每次写完add都对着 4.2 的表格读一遍从起点开始每把一个坐标换成终点加一符号就翻转一次改 0 个是正改 1 个是负改 2 个是正改 3 个是负。第四个是还原时忘记diff[i][j] 这种“原地更新”的写法而是新开一个sum数组。新开数组不是不行但反而容易在对应下标时出错。直接在diff上做前缀和最后diff[i][j]就是最终答案简单直接。最后一个就是下标习惯。差分题目几乎清一色用 1-based 下标务必在读取原始数组和输出答案时把 0-based 和 1-based 的换算做对。LeetCode 这类平台经常给你 1-based 的输入和 0-based 的输出这种错位问题通常很隐蔽但造成的返工成本最高。说实话差分数组这个知识点的门槛并不高只需要把“区间操作转端点操作”这个思维转过弯一维、二维、三维其实都是同一个套路。真正难的是在实际题目里判断出该用差分以及在三维空间里不慌不乱地写出八个角标。我个人建议你用这篇文章里的模板去刷三道题验证一下一维做 LeetCode 1109二维做洛谷 P3397三维找一道“三体攻击”或者类似的三维差分题。第一次写三维add的时候对照符号表一步一步来写完之后自己造一组小数据手工验算一遍这个过程比背十遍模板都有用。等你能不假思索地写出三维差分的add和还原循环时这个知识点才算真正被你“手撕”下来了。之后遇到矩形覆盖、立方体批量伤害、区间增量统计这类问题你会在别人还在想暴力怎么优化的时候直接写下一行add(l, r, c)。