区间加、矩阵加、空间体块加权这类“对一整块区域批量更新”的需求在算法题和工程项目里出现频率非常高。但很多人真上手写代码时才发现暴力改每个点根本跑不动这时候差分数组就是最顺手的解法。差分数组和前缀和是一对互逆操作它的核心价值是把一次区间级别的批量更新压缩成常数个点的修改最后再通过一次前缀和把完整结果恢复出来。这篇文章我会把一维、二维、三维差分数组的原理、图解、模板代码和例题一次性讲透包括我自己写二维、三维时踩过的那些坑也会一并复盘。1. 从朴素操作到差分思想为什么非要“手撕”差分1.1 你遇到的是哪种“批量更新”先看几个真实场景。一维场景很好理解一个长度为 n 的数组执行 q 次“给 [l, r] 区间内每个数加 v”的操作最后输出完整数组。二维场景也不难想到一个 n 行 m 列的矩阵执行 q 次“给某个子矩形区域全部加 v”的操作最后输出矩阵。三维场景稍微抽象一点但做三维目标检测、三维点云体素化、医学影像处理的人经常会碰到一个 n×n×n 的立方体数据执行 q 次“给某个长方体区域全部加 v”的操作最后再做查询或输出。这三种问题有一股共同的味道更新的是“一整块连续区域”而不是单个点。暴力做当然简单但复杂度是致命的。一维暴力一次区间更新是 O(n)二维一次子矩阵更新是 O(n*m)三维一次长方体更新是 O(n³)。当 n 和 q 都到 1e5 甚至 1e4 时运算量轻松破亿甚至破十亿普通电脑基本吃不消。差分数组就是为这种问题准备的。它把一次区间更新的复杂度从 O(区域大小) 降到 O(1)最后只需要一次总恢复总复杂度大概就是 O(数组总元素数 操作次数)。换句话说不管执行多少次更新最终扫描一遍数组就够了这就是“手撕差分”的核心意义。1.2 差分与前缀和一对互逆操作前缀和和差分是一对“天生互逆”的操作。前缀和是把原数组从左到右累加得到每个位置之前的累积值差分则是计算数组中每个位置和上一个位置的差值。一维前缀和公式是pre[i] pre[i - 1] a[i]一维差分数组的定义就是相邻元素之差diff[i] a[i] - a[i - 1]如果你对 diff 再做一次前缀和就会惊奇地发现得到的就是原数组 a。这就是“互逆”的含义。生活里可以把它理解成“流水账”。前缀和就是记账本上每一笔发生之后的账面总额差分则是每一笔单独的收支变化。单独看 diff你可能不知道总额是多少但只要把前面所有 diff 累加起来账面总额就立刻出来了。用差分做区间更新只需要抓住一个关键点数组 diff 是“变化量”的累积源。对区间 [l, r] 每个数加 v其实等价于在位置 l 加一个 v 作为“上升台阶”在位置 r 1 减一个 v 作为“收尾台阶”。最后从左往右把 diff 累加一遍每个位置得到的累加值就是该位置在所有更新中收到的净变化。1.3 为什么二维、三维不是“照着套”就行一维差分看起来很简单好像只要记住“l 加 vr 1 减 v”就够了。但到了二维、三维很多第一次接触的人会想是不是在矩形的左上角加 v右下角减 v 就行答案是不行。因为二维前缀和本身是有容斥关系的二维差分做区域更新时也要对应地处理四个角、八个顶点。这背后的统一规律是维度是 d区域更新的“边界修正点”就有 2^d 个。一维是 2 个点二维是 4 个点三维是 8 个点。每个点的符号由该点在每个维度上是否取了“上界 1”决定取“上界 1”的个数为偶数时取正号奇数时取负号。这个规律在后面的章节里我会反复用到也是手写高维差分时最不容易出错的方法。理解了这个规律你会发现二维、三维差分并不是新知识只是一维差分的自然推广只是多了一个“容斥”的意识。2. 一维差分数组原理、图解与模板2.1 一维差分数组的定义与区间更新推导一维差分数组的定义很简单。给定长度为 n 的数组 a下标从 1 开始定义diff[1] a[1] diff[i] a[i] - a[i - 1]i ≥ 2对这个 diff 做前缀和 sum[i] diff[1] diff[2] ... diff[i]代入 diff 的定义会发现中间的项全部抵消最后只剩下 a[i]。这就是“差分是前缀和的逆运算”的直观证明。区间更新的推导也不复杂。假设要对 [l, r] 区间内每个数加 v我们直接修改 diffdiff[l] v diff[r 1] - v为什么是这两个位置因为恢复时会对 diff 做前缀和。从位置 l 开始累加值突然多了一个 v那么 l、l1、...、r 这些位置在恢复时都会多出 v到了 r 1由于这里减了 v累加值又被拉回原来的水平所以 r 之后的位置不受影响。画图来看就更直观了。想象一条水平线表示“当前累计变化量”在位置 l 处向上跳一格加 v保持这个高度一直走到 r在 r 1 处再落回原来的高度减 v。最终这条折线覆盖的区间就是 [l, r] 整体加 v 的效果。这里有个小细节特别值得注意r 1 可能等于 n 1这没问题。恢复的时候前缀和只需要做到第 n 位n 1 位置的减 v 只是用来结束区间不需要真的输出它。但 diff 数组一定要开够大小最好开 n 2避免越界。2.2 一维差分模板代码与两种写法下面给一个 C 的完整模板下标从 1 开始用 add 函数统一处理更新。#include bits/stdc.h using namespace std; const int N 100005; long long a[N], diff[N]; void add(int l, int r, long long v) { diff[l] v; diff[r 1] - v; } int main() { int n, q; cin n q; for (int i 1; i n; i) { cin a[i]; add(i, i, a[i]); // 把初始值也当作单点更新 } while (q--) { int l, r; long long v; cin l r v; add(l, r, v); } // 前缀和恢复结果直接覆盖在 a 上 for (int i 1; i n; i) { diff[i] diff[i - 1]; a[i] diff[i]; cout a[i] \n[i n]; } return 0; }这里我故意用 add(i, i, a[i]) 来构建差分而不是用公式 diff[i] a[i] - a[i - 1]。原因很简单构建差分数组本身也是“一次区间更新”复用同一个 add 函数代码更简洁而且不容易记错容斥公式。这个习惯在二维、三维下尤其好用因为二维、三维的容斥公式又长又容易错统一用 add 来初始化能省掉很多麻烦。Python 版本也很短def add(l, r, v, diff): diff[l] v diff[r 1] - v n, q map(int, input().split()) a list(map(int, input().split())) diff [0] * (n 2) for i, x in enumerate(a, start1): add(i, i, x, diff) for _ in range(q): l, r, v map(int, input().split()) add(l, r, v, diff) for i in range(1, n 1): diff[i] diff[i - 1] print(diff[i], end )C 里还有两个常见坑一是用 0-index 还是 1-index一定要全篇统一二是在函数里传数组时如果不想写全局变量最好用 vector 或指针。如果你用 C 语言写二维数组再传给函数就必须在形参里写上列数否则编译器不知道一行多长。2.3 一维差分的典型使用场景一维差分应用最多的场景是“多次区间更新最后一次性查询”。最典型的题目就是航班预订统计n 个航班若干条预订记录每条记录表示给第 first 到 last 个航班增加 seats 个预订数最后返回每个航班的总预订数。这种场景不止出现在算法题里。公交车站客流统计可以理解为“每辆公交车在起始站人数增加在终点站的下一站人数减少”温度传感器的时间序列批量修正也可以看成对连续时间段做偏移。只要数据是“一维序列 区间批量修改 最后汇总”差分就是第一选择。需要提醒一句差分适合离线场景。如果操作是“边修改边查询”比如每次更新后立刻问某个点的值那就不适合用差分因为差分恢复是整个数组一起做的单点查询需要先恢复。这种在线场景应该用线段树或树状数组别拿着差分硬套。3. 二维差分数组原理、图解与模板3.1 二维差分数组定义与二维前缀和的逆关系二维的问题从一维推广过来核心变化是恢复过程从一维前缀和变成了二维前缀和。先回顾二维前缀和公式。设原矩阵为 a前缀和矩阵为 s则s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1] a[i][j]这个公式里有一个 - s[i - 1][j - 1]因为 s[i - 1][j] 和 s[i][j - 1] 都包含了 s[i - 1][j - 1] 这份重叠区域必须减去一次。既然前缀和公式里有容斥那二维差分作为前缀和的逆运算也一定会带着容斥。二维差分数组的定义就是把这个公式反过来diff[i][j] a[i][j] - a[i - 1][j] - a[i][j - 1] a[i - 1][j - 1]验证方法很简单对 diff 再做一次二维前缀和所有中间项相互抵消最终得到原矩阵 a。3.2 子矩阵加v的4点更新与图解现在问题是要让从 (x1, y1) 到 (x2, y2) 的子矩阵内每个元素加 v差分矩阵 diff 应该怎么改答案是四个点diff[x1][y1] v diff[x2 1][y1] - v diff[x1][y2 1] - v diff[x2 1][y2 1] v四个点的位置和符号可以画成下面这样(x1, y1) v (x1, y2 1) -v (x2 1, y1) -v (x2 1, y2 1) v为什么是四个点因为二维前缀和的恢复过程是从左上角往右下角一层层累加的。我们在 (x1, y1) 放一个正 v那么从 (x1, y1) 开始向右下方扩散的所有位置都会加 v这显然会把矩形以外的很多区域也加上 v所以要在 (x2 1, y1) 和 (x1, y2 1) 分别放一个负 v把下方和右方的错误扩散“切断”。但这两个负 v 的扩散范围会在 (x2 1, y2 1) 处重叠导致该区域被减了两次所以最后还要在 (x2 1, y2 1) 放一个正 v把多减的那一次补回来。这个解释其实就是二维容斥。记忆方法也很简单左上角为正右下角也为正另外两个角为负。如果你熟悉二维前缀和的容斥公式会发现差分更新的符号和它天然对应。我在纸上画过很多次这个图。第一次手推时总觉得右下角应该是负号结果恢复出来整个矩形外右下方的区域都少了值。后来记住“四个点的符号只看每个点取到上界的次数偶数正、奇数负”就再也没错过。3.3 二维差分完整模板代码与封装技巧下面是一个完整的二维差分模板支持 n 行 m 列矩阵q 次子矩阵加值最后输出完整矩阵。#include bits/stdc.h using namespace std; const int N 1005; long long diff[N][N]; 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; scanf(%d%d%d, n, m, q); // 初始化读入原始矩阵并当作若干次单点更新 for (int i 1; i n; i) { for (int j 1; j m; j) { long long x; scanf(%lld, x); add(i, j, i, j, x); } } while (q--) { int x1, y1, x2, y2; long long v; scanf(%d%d%d%d%lld, 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]; } } for (int i 1; i n; i) { for (int j 1; j m; j) { printf(%lld , diff[i][j]); } puts(); } return 0; }这个模板有几个细节。第一我依然用 add(i, j, i, j, x) 来处理初始矩阵这样整个程序只有一个 add 函数不需要另外写构建差分的容斥代码。第二diff 数组必须开大一圈避免 x2 1、y2 1 越界。这里开的是 N 1005实际大小只要比 n/m 的最大值各多 1 以上即可。第三恢复时公式用的是二维前缀和公式。注意这里的求和是原地累加因此最终 diff[i][j] 保存的就是原矩阵加上所有更新后的最终值。另外如果使用 C 语言并在函数之间传递二维数组形参必须指定列数比如 void add(int n, int m, int diff[][N], ...)否则数组在函数内部会退化成指针无法正确索引。这也是二维数组和 C 语言传参里最常见的坑。3.4 二维差分数组的高频使用场景二维差分最常见的场景是矩阵区域批量操作。图像处理里给某个 ROI 区域统一增加亮度地图应用里给一片矩形区域统一标记某种属性游戏开发里给一张二维网格地图上某个矩形区域增加事件计数。这些都可以用二维差分先离线记录更新最后统一恢复成最终的矩阵。二维差分和二维前缀和一样在“二维数组排序”“二维字符数组处理”这类问题里也会作为前置工具出现。比如你需要对若干矩形区域做加值后再对结果按行做某种排序二维差分先把结果矩阵跑出来再交给 sort 去处理整个流程就非常干净。4. 三维差分数组原理、图解与模板4.1 三维差分与三维前缀和的推导三维差分是在三维网格上做批量更新。它比二维又多了一个维度容斥项也更多但前一节说的“维度为 d更新点 2^d 个”的规律依然成立。先看三维前缀和公式。设三维数组为 a[i][j][k]前缀和为 s[i][j][k]则s[i][j][k] a[i][j][k] s[i - 1][j][k] s[i][j - 1][k] s[i][j][k - 1] - s[i - 1][j - 1][k] - s[i - 1][j][k - 1] - s[i][j - 1][k - 1] s[i - 1][j - 1][k - 1]三维前缀和有三个正的相邻项减去三个两两重叠项再加回三个都重叠的那一项。三维差分就是把这个公式反过来定义diff[i][j][k] a[i][j][k] - a[i - 1][j][k] - a[i][j - 1][k] - a[i][j][k - 1] a[i - 1][j - 1][k] a[i - 1][j][k - 1] a[i][j - 1][k - 1] - a[i - 1][j - 1][k - 1]符号怎么记和前缀和公式的正负号完全对应没有减号的项为正有一个减号的相邻项为负有两个减号的重叠项为正有三个减号的三重重叠项为负。4.2 长方体加v的8点更新公式与图解现在要让从 (x1, y1, z1) 到 (x2, y2, z2) 的长方体内所有点加 v。三维差分更新需要修改 8 个点每个点的坐标分别在 x、y、z 三个维度上选择“下界”或“上界 1”。8 个点的更新如下diff[x1][y1][z1] v diff[x2 1][y1][z1] - v diff[x1][y2 1][z1] - v diff[x1][y1][z2 1] - v diff[x2 1][y2 1][z1] v diff[x2 1][y1][z2 1] v diff[x1][y2 1][z2 1] v diff[x2 1][y2 1][z2 1] - v这个表看着很吓人实际上用二进制位来记就非常简单。把三个维度分别看成二进制位当前维坐标取下界记为 0取“上界 1”记为 1。那么 8 个点正好对应 000 到 111。符号规则是三个标志位中 1 的个数为偶数时取正号为奇数时取负号。验证一下000 有 0 个 1正100x 取上界 1有 1 个 1负110x、y 都取上界 1有 2 个 1正111 有 3 个 1负。这和表格完全一致。如果硬要画图想象一个长方体八个顶点上分别标着 或 -。符号相同的顶点在对角位置看起来像三维棋盘。恢复时对 diff 做三维前缀和长方体内部恰好每家都分到一个 v长方体外部被正负点互相抵消净变化是 0。4.3 三维差分模板代码与内存注意点三维差分代码和二维非常相似只是循环从两层变成三层更新点从 4 个变成 8 个。下面是一个可直接运行的框架#include bits/stdc.h using namespace std; const int N 105; int n, m, p; long long diff[N][N][N]; void add(int x1, int y1, int z1, int x2, int y2, int z2, long long v) { diff[x1][y1][z1] v; diff[x2 1][y1][z1] - v; diff[x1][y2 1][z1] - v; diff[x1][y1][z2 1] - v; diff[x2 1][y2 1][z1] v; diff[x2 1][y1][z2 1] v; diff[x1][y2 1][z2 1] v; diff[x2 1][y2 1][z2 1] - v; } void restore() { for (int i 1; i n; i) { for (int j 1; j m; j) { for (int k 1; k p; 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]; } } } } int main() { int q; scanf(%d%d%d%d, n, m, p, q); for (int i 1; i n; i) for (int j 1; j m; j) for (int k 1; k p; k) { long long x; scanf(%lld, x); add(i, j, k, i, j, k, x); } while (q--) { int x1, y1, z1, x2, y2, z2; long long v; scanf(%d%d%d%d%d%d%lld, x1, y1, z1, x2, y2, z2, v); add(x1, y1, z1, x2, y2, z2, v); } restore(); // 输出某个点或按需遍历结果 int x, y, z; scanf(%d%d%d, x, y, z); printf(%lld\n, diff[x][y][z]); return 0; }三维差分最需要注意的不是公式是内存。n、m、p 都是 100 时数组大小是 100³ 1e6long long 占 8 字节也就是 8MB还好。但如果 n、m、p 到 300数组大小是 2700 万long long 直接飙到 216MB很容易爆内存。这时要么把类型换成 int值域允许的话要么用 vector 动态申请vectorvectorvectorlong long diff( n 2, vectorvectorlong long(m 2, vectorlong long(p 2, 0)));动态 vector 的好处是尺寸由输入决定不会因为开太大而浪费内存写起来也没有多复杂。4.4 从竞赛题到三维视觉/GIS三维差分的应用视野三维差分在竞赛里常作为高阶模板出现但在工程和科研场景里它同样很实用。三维点云体素化之后每个体素是一个小格子。如果你想给某个长方体包围盒内的所有体素统一增加一个计数三维差分就能一次标记整个区域避免逐个体素循环。三维目标检测里需要批量给候选框内部的体素赋标签或加权值三维差分是很好的离线预处理工具。三维 GIS 中对某片三维空间区域的属性做批量更新比如将某个矿体范围内的体素标记为特定值也可以用三维差分。还有一个更直观的场景二维图像生成三维模型时先从多视图重建出体素网格后续经常需要在局部做“膨胀”“挖空”“填充”。如果用三维差分记录这些批量改动最后一次恢复整个模型的体素状态就能瞬间更新完不用对每个体素重复读写。理解和掌握三维差分不只是为了刷题更是为这些三维数据处理任务打底。5. 例题分析从模板到实战5.1 一维例题航班预订统计题目是这样的有 n 个航班编号从 1 到 n。给定一个预订列表 bookings其中 bookings[i] [first, last, seats] 表示第 i 条预订记录会给第 first 到第 last 个航班每个增加 seats 个预订量。请返回一个长度为 n 的数组 answeranswer[i] 表示第 i 1 个航班的总预订数。经典差分题。每个预订记录就是一次区间更新 [first, last] 加 seats。我们在 diff 数组上做diff[first] seats diff[last 1] - seats最后从左到右累加前缀和累加值就是每个航班的最终预订数。C 写法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], v b[2]; diff[l] v; diff[r 1] - v; } vectorint ans(n); int cur 0; for (int i 1; i n; i) { cur diff[i]; ans[i - 1] cur; } return ans; } };这道题的变式也很多。公交站客流统计就是一个典型给定每条线路的起点站、终点站和上车人数问每个站最多有多少人。本质就是把“区间加”换成“上下车人数变化”最后扫一遍即可。做这类题有一个经验如果题目给的是 1-index 的区间diff 数组直接开成 n 2下标从 1 开始用如果给的是 0-index就统一把下标整体偏移到 1-index或者严格按 0-index 处理千万不要一个程序里混用。5.2 二维例题矩形区域加并输出最终矩阵题目给定一个 n 行 m 列的矩阵初始所有元素为 0。执行 q 次操作每次输入 x1, y1, x2, y2, v表示将子矩阵 (x1, y1) 到 (x2, y2) 内所有元素加 v。所有操作结束后输出最终矩阵。这就是二维差分的模板题。直接调用 add 更新四个点最后做二维前缀和恢复。#include bits/stdc.h using namespace std; const int N 1005; long long diff[N][N]; 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; scanf(%d%d%d, n, m, q); while (q--) { int x1, y1, x2, y2; long long v; scanf(%d%d%d%d%lld, 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]; for (int i 1; i n; i) { for (int j 1; j m; j) printf(%lld , diff[i][j]); puts(); } return 0; }如果初始矩阵不是 0就额外加一步读入初始值 x 后调用 add(i, j, i, j, x)。这样原矩阵的值会先进入 diff最后恢复时自动叠加在结果里。这个技巧在二维、三维的题目里都适用强烈建议养成习惯。这个模板题的复杂度是 O(nm q)。如果 n、m 都是 1000q 是 1e5总的计算量也就百万级别跑起来非常快。但注意输出本身是 O(nm)这已经是理论下限了不可能再省。5.3 三维例题立方体区域加并查询点值题目给定一个 n×n×n 的立方体初始所有点值为 0。执行 q 次操作每次输入 x1, y1, z1, x2, y2, z2, v表示将长方体区域 (x1, y1, z1) 到 (x2, y2, z2) 内所有点加 v。所有操作结束后查询某个点 (x, y, z) 的值。三维差分模板直接就能解。更新部分调用 add 的 8 点更新最后做三维前缀和恢复。核心代码框架vectorvectorvectorlong long diff( n 2, vectorvectorlong long(n 2, vectorlong long(n 2, 0))); auto add [](int x1, int y1, int z1, int x2, int y2, int z2, long long v) { diff[x1][y1][z1] v; diff[x2 1][y1][z1] - v; diff[x1][y2 1][z1] - v; diff[x1][y1][z2 1] - v; diff[x2 1][y2 1][z1] v; diff[x2 1][y1][z2 1] v; diff[x1][y2 1][z2 1] v; diff[x2 1][y2 1][z2 1] - v; }; // 恢复三重循环做三维前缀和 for (int i 1; i n; i) for (int j 1; j n; j) for (int k 1; k n; 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]; } // 查询 printf(%lld\n, diff[x][y][z]);这里用 lambda 封装 add可以省去把多维数组传给函数的麻烦闭包里可以直接捕获外部的 diff写起来很顺手。如果编译器支持 C17这种写法在竞赛里很实用。三维例题的复杂度是 O(n³ q)。n 较大时恢复过程本身就会成为性能瓶颈所以三维差分适合“更新多、但网格规模可控”的场景。6. 差分高频踩坑与调试技巧6.1 六个常见错误与修复我自己最早写差分的时候几乎把能踩的坑都踩了一遍。这里整理成速查表供大家对照。错误现象原因分析修复方法下标越界程序崩溃r 1、x2 1、z2 1 等于 n 1 或超出维度diff 数组在每个维度多开至少 1 到 2 个空间结果出现“断层”局部多加了或少加了更新公式里的符号写错比如二维右下角写成了负号用“1 的个数奇负偶正”口诀逐点检查更新点0-index 和 1-index 混用输入下标是 0 开头代码里却按 1 开头处理统一转换成 1-index或统一使用 0-index输出结果没包含初始值只记录了后续更新没把原数组初始值加进 diff把初始值也当作若干次单点 add 处理二维数组传给函数后访问越界或结果错乱C 语言传二维数组没有指定列数指针运算出错形参写成 diff[][N]或使用 vector三维程序内存爆炸n 较大long long 数组直接开满改用 int或使用动态 vector6.2 调试差分代码的3个实用技巧差分代码出错时肉眼很难定位尤其是三维的 8 个更新点。我建议按下面三步来排查。第一写一个暴力版本对拍。随机生成小规模数据比如一维 n10、二维 5×5、三维 4×4×4分别用暴力和差分跑一遍随机执行几次更新逐项比对结果。这个办法能发现绝大多数逻辑错误而且不需要手算。第二打印中间过程。在小数据下分别打印 diff 数组更新前后的值以及每次前缀和恢复后的中间结果。对照手算能很快看出是更新点放错了位置还是恢复公式写错了符号。第三用 Python 或 MATLAB 做快速验证。Python 里可以用 numpy 的 diff 和 cumsum 快速验证一维公式MATLAB 里也有现成的 diff 和 cumsum 函数先拿它们把二维、三维更新的正确性验证一遍再转换成 C 代码。这样可以把“公式推导错误”和“代码实现错误”分开排查定位速度会快很多。6.3 一些实战心得最后分享一个我自己的习惯就是始终把差分数组理解成“施工计划表”而不是“最终结果”。数组里每个点的初始值、每次区间更新都是往计划表里写入一条施工指令最终的前缀和恢复才是按照计划表把工地实际建成的过程。写代码时只要分清“指令层”和“结果层”很多混淆就自动消失了。另外从一维到三维模板的骨架其实完全一样add 函数负责在 2^d 个点写指令restore 函数负责做对应维度的前缀和。真正需要死记的只有每个维度的更新点数量和符号规则。一维 2 个点、二维 4 个点、三维 8 个点符号看“1 的个数”这套方法我用了很久基本不会出错。