前阵子处理一个数据统计需求时遇到了一个很典型的场景一张1000×1000的网格图要在上面叠加几十万个矩形区域的权重最后输出每个格子的最终数值。第一版用暴力循环遍历每个矩形覆盖到的格子数据量一大完全跑不动后来换成二维差分数组同样的任务从分钟级降到了毫秒级。如果你也遇到过“给矩阵的某个矩形区域批量加值最后一次性查询每个位置的值”这类问题那这篇文章正好对路。二维差分数组的原理并不复杂它是二维前缀和的逆运算专门解决“多次矩形整体修改 最终统一查询”的离线场景。竞赛选手刷区域覆盖题会用到做数据统计、图像处理的工程里同样能用上。下面我把它的原理推导、代码模板、性能对比、边界坑位一次讲清楚。1. 需求来源给矩形区域批量加值到底难在哪先别急着看公式我们从问题本身出发。假设有一张n行m列的矩阵初始全为0。现在要执行q次操作每次操作把一个子矩形区域内的所有格子加上同一个数值v比如把第2行到第5行、第3列到第7列这个矩形区域全部加3。所有操作完成后需要得到矩阵中每个位置最终的数值。1.1 一个具体的需求网格区域加权统计我当时的业务场景是线下活动的区域热力统计把一个会场划分成网格每场活动会占用一个矩形区域要给这个区域内的每个格子增加一次覆盖次数。几十万场活动标记完之后最终要输出整张会场的覆盖热力图。再举个例子图像处理里如果要把多个矩形区域的亮度同时提高也是同一类操作每个像素点就是一个格子矩形ROI区域就是待修改的区块。这类问题有一个共同特征操作次数多、矩阵规模大、但查询只在最后发生一次。如果直接用暴力做法一次矩形更新的代价是(x2 - x1 1) * (y2 - y1 1)也就是矩形面积。当矩形个数多、面积又大的时候总操作量会迅速膨胀到不可接受。1000×1000的网格50万个平均面积为10000的大矩形暴力算下来就是50亿次操作基本告别“实时出结果”这件事了。1.2 一维差分先立个样板二维差分的前身是一维差分建议在理解二维之前先把一维模型彻底吃透。一维数组a长度n要进行m次区间操作每次把[l, r]内的元素全部加上v。暴力做法是遍历l到r逐个加v一次操作O(n)。差分做法的核心是构造一个差分数组d让区间加法变成对d的常数次修改d[l] v; d[r 1] - v;所有区间操作完成后对d从头到尾做一次前缀和就能还原出每个位置被加了多少for (int i 1; i n; i) { d[i] d[i - 1]; a[i] d[i]; }这里的直觉可以这样理解d[l] v表示从位置l开始后续所有前缀和结果都会多出一个v而d[r1] - v表示累加到r1时v的影响被抵消所以真正被影响到的只有闭区间[l, r]。我以前带新人时发现很多人对一维差分里“为什么要在r1处减掉v”有点懵。其实只要对比前缀和的累加过程就明白了前缀和是带记忆的它会把之前所有差分值一路带下去所以“开始加”和“结束减”这两个标记之间的距离就是区间覆盖的范围。1.3 从“区间”到“矩形”的维度跳跃一维差分解决的是线段上的区间覆盖二维差分解决的是平面上的矩形覆盖。核心思想完全一样把“对一个区域的整体修改”转化为“对几个特殊点的修改”最后通过一次前缀和把影响扩散出去。一维区间有两个端点所以是“起点加、终点后一个位置减”两个标记。二维矩形有四个角对应的标记操作从2个变成了4个。这个跳跃在数学上是自然的——二维前缀和本身就是两个维度上的累计所以反向构造差分时也需要在两个维度上分别做“开始”和“结束”的标记。2. 四个标记点怎么来的从二维前缀和反推差分公式差分是前缀和的逆运算。想理解二维差分的四个标记点必须先看懂二维前缀和是怎么算的。2.1 二维前缀和的累加规则给定一个矩阵A它的二维前缀和S定义为S[i][j]表示从(1,1)到(i,j)这个子矩阵内所有元素的和。递推公式是S[i][j] A[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1]这个公式用到了容斥原理S[i-1][j]覆盖了上方区域S[i][j-1]覆盖了左方区域两者相加后S[i-1][j-1]这块左上角区域被算了两次所以要减掉一次。如果你想把S还原成A公式就是A[i][j] S[i][j] - S[i-1][j] - S[i][j-1] S[i-1][j-1]这是二维前缀和的逆运算。而二维差分的构造思路正好反过来我们已知每个位置的增量想找出一个差分矩阵D使得对D做二维前缀和之后得到这个增量矩阵。2.2 从约束条件反推差分标记公式假设我们希望在子矩阵(x1, y1)到(x2, y2)内的每个位置增加v。对D做二维前缀和时D中某个位置的值会向“右下方”的所有位置传播。为了精确控制传播范围我们在四个关键位置打上标记D[x1][y1] v D[x1][y21] - v D[x21][y1] - v D[x21][y21] v第一眼看上去这个“ - - ”的符号分布有点反直觉。我换个角度解释一下。前缀和的传播方向是向右下。在D[x1][y1]加v所有行坐标大于等于x1、列坐标大于等于y1的位置都会收到这个v。但这远远超出了目标矩形所以需要把它拦腰截断。在D[x21][y1]减掉v等于告诉前缀和“从x21这一行开始之前那个v的影响要终止”。但是这一减会把x21行往右的所有列也一起减掉包括目标矩形右侧下方那些本来不该受影响的位置。于是还需要在D[x1][y21]减掉v把y21列右侧的影响终止。现在目标矩形的右下方区域同时被这两个减法影响了从(x21, y1)进来的减法和从(x1, y21)进来的减法在(x21, y21)的右下方重叠等于被多减了一次。为了纠正这个重叠区域的偏差最后在D[x21][y21]加回v。所以“ - - ”的本质是两次一维截断的交叉区域修正和二维前缀和公式里的容斥是同一套逻辑。我建议你拿一张方格纸手工画一个4×4的矩阵在(2,2)到(3,3)这个矩形上做一次标记然后逐格做前缀和亲眼看一下四个标记点如何约束传播范围。这个手动推演比背公式可靠得多。2.3 直观记忆把矩形看成两组一维区间还有另一个记忆方式矩形的行区间是[x1, x2]列区间是[y1, y2]。把二维差分看作“先处理行的差分再处理列的差分”。如果只从行的维度看x1行要“开始”x21行要“结束”从列的维度看y1列要“开始”y21列要“结束”。四个角就是两个维度上“开始/结束”的四种组合。组合符号由“开始”计为、“结束”计为-决定(x1,y1)是(x1,y21)是-(x21,y1)是-(x21,y21)是。这个记忆法在扩展到三维时同样受用后面第七章会提到。3. 完整实现add操作与一次前缀和还原理论推导完了直接上代码。下面是我在实际工程和竞赛里都在用的模板按1-based下标编写也就是矩阵的行列从1开始编号。3.1 C实现模板#include bits/stdc.h using namespace std; using ll long long; const int MAXN 1005; ll diff[MAXN][MAXN]; int n, m; // 矩阵行数、列数 // 子矩阵 (x1,y1) 到 (x2,y2) 内所有格子的值增加 v void add(int x1, int y1, int x2, int y2, ll v) { diff[x1][y1] v; diff[x1][y2 1] - v; diff[x2 1][y1] - v; diff[x2 1][y2 1] v; } // 所有add操作完成后对diff做二维前缀和原地还原增量矩阵 void build() { 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]; } } }注意build()里是在原数组上原地做前缀和结果直接存在diff里。这里的diff下标从1开始第0行第0列保持为0是为了让diff[i-1][j]在边界时不会越界访问。3.2 Python版本与下标习惯如果你用Python刷题或做数据分析核心逻辑完全一样def add(x1, y1, x2, y2, v): diff[x1][y1] v diff[x1][y2 1] - v diff[x2 1][y1] - v diff[x2 1][y2 1] v def build(): for i in range(1, n 1): for j in range(1, m 1): diff[i][j] diff[i - 1][j] diff[i][j - 1] - diff[i - 1][j - 1]Python里要注意的是diff矩阵建议初始化为(n 2) * (m 2)大小的二维列表避免add操作访问到x21或y21时出现IndexError。3.3 手算验证一个4×4的小例子空口无凭我带你推一遍。有一个4×4的矩阵初始全0。现在执行一次操作把(2,2)到(3,3)这个2×2的子矩阵全部加1。add操作之后diff矩阵的非零位置如下第2行第2列1 第2行第4列-1 第4行第2列-1 第4行第4列1然后对diff做二维前缀和得到的增量矩阵应该是0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0如果加一个耗时操作比如add(1,1,2,2,1)和add(2,2,3,3,2)叠加最终还原出来的矩阵会是什么留给你自己动手跑一下。这是检验自己是否真正理解二维差分最直接的方式手动推演两个矩形重叠的标记和还原结果全程不碰代码。3.4 原矩阵有初始值时的处理方式上面讲的模板假设初始矩阵全为0差分矩阵记录的纯粹是增量。如果原矩阵本身有数值有两种处理思路。第一种最简单也最不容易出错差分矩阵只记录增量最后把原始矩阵和增量矩阵相加for (int i 1; i n; i) for (int j 1; j m; j) ans[i][j] base[i][j] diff[i][j];第二种把原始矩阵也看作“点更新”的叠加即对每个base[i][j]执行一次“单点加”的差分标记。单点加本身就是把矩形退化成(i,j)到(i,j)的特例四个标记点都落在同一个顶点上。但这样会让add操作数量变成n*m q当矩阵很大时反而更慢。我个人的建议是不要玩花活直接方案一。多开一个矩阵不会让内存压力大到哪去但逻辑清晰度提升是实打实的。4. 复杂度与性能边界这个算法的收益到底有多大二维差分数组的复杂度分析很简单但很多人没意识到它真正的优势区间在哪里。4.1 暴力、差分的复杂度拆解暴力做法每次矩形更新遍历区域内所有格子单次成本是(x2-x11)*(y2-y11)最坏情况下等于整个矩阵面积n*m。q次操作后总复杂度是O(q*n*m)。二维差分做法每次矩形更新只做常数次数组加减单次成本O(1)。所有操作完成后做一次二维前缀和成本是O(n*m)。总复杂度是O(q n*m)。关键区别在于暴力里q和n*m是相乘的关系差分里它们是相加的关系。当q和矩阵面积都很大时这个差距是指数级的。4.2 实际数据对比我专门写了个脚本测试n1000, m1000执行10万次随机矩形加值操作的耗时对比方案时间复杂度1000×1000矩阵、10万次更新的估算耗时暴力遍历矩形O(q × 矩形面积)最坏约1e11次加法分钟级以上二维差分O(q n×m)约1.4e6次运算毫秒级1e11次加法是什么概念普通CPU一秒钟大概能跑几亿次简单整数运算1e11次加法理论耗时也得几十秒到几分钟。而差分方案里10万次矩形更新的标记操作只有40万次加减加上100万次的二维前缀和还原总共140万次运算一毫秒到几毫秒就能跑完。4.3 内存与优化思路差分矩阵需要(n2)*(m2)的空间。如果矩阵是1000×1000用long long存储大约8MB完全可以接受。但如果矩阵尺寸达到1万×1万差分矩阵需要400MB以上这就有点紧张了需要考虑更节省内存的方案。内存吃紧时有一个思路如果矩形个数相对较少可以先把所有add操作的四个标记点离线存下来按坐标排序后统一累加避免开完整的差分矩阵。这种做法适合矩阵巨大但操作数较少的场景属于用时间换空间。不过大多数情况下直接开差分矩阵就够了不必过度优化。5. 三个典型应用场景刷题、业务统计与图像处理原理和实现都聊完了看几个实际用得上二维差分的场景。5.1 竞赛场景区域覆盖计数算法题里最常见的考法就是“给你一堆矩形求每个格子被覆盖了多少次”。比如碰到的这类题一个n×n的网格输入m个矩形的左上角和右下角坐标每个矩形覆盖到的格子计数加1最后输出整个网格的覆盖情况。这类题用二维差分几乎是送分题。每次给一个矩形做add操作最后build一次再输出每个格子的值就行了。我建议第一次接触二维差分的人找一两道这样的简单题作为练手入口重点不是为了AC而是验证自己对四个标记点的理解是否到位。5.2 业务统计线下活动的区域加权回到开头提到的会场热力统计。每场活动占用一个矩形区域要统计每个展位的覆盖次数。用二维差分每场活动只记录四次标记最后统一还原几十万场活动的数据量也能轻松处理。这类离线批量统计场景非常契合二维差分的特性操作量大、中间不查询、只在最后做一次总量计算。如果业务中还需要“边更新边查询”二维差分就不够用了后面第七章会展开说。5.3 图像处理多个ROI区域批量增强图像本质上就是一个二维矩阵。要对多个矩形ROI区域做灰度增强可以先用二维差分记录每个像素点的亮度增量最后一次性叠加到原图上。相比逐像素循环处理差分方案会让整体计算链路简洁很多尤其是在ROI数量多、区域面积大的情况下。需要注意的是图像处理中的常见坐标系以左上角为原点行列都是从0开始编号。用差分时要处理好下标偏移确保add操作访问的下标都在数组范围内。6. 最容易翻车的边界与调试经验二维差分的代码量很少但正因为代码量少出错了反而不容易一眼看出问题。下面几个坑是我自己踩过也看别人踩过无数次的。6.1 数组一定要多开一圈add操作里会出现x2 1和y2 1。如果x2恰好等于矩阵最后一行n那么就要访问diff[n1][...]这一行。所以数组至少需要(n2)*(m2)大小不能只开到(n1)*(m1)更不能只开到n*m。我之前用C写题时数组开成MAXN][MAXN]但MAXN只比n大1结果add访问到diff[n1]时越界程序行为完全随机。这类越界问题在本地小数据时可能不触发数据一大就崩。养成习惯凡是处理差分数组无脑多开两格省去排查越界的时间。6.2 用long long防止溢出如果每次加的值v很大、操作次数q很多单个格子的最终值可能远超int范围。比如1000×1000矩阵50万次操作每次加10000理论上一个格子可能被所有操作覆盖最终值达到50亿已经超过int的21.47亿上限。所以只要v和q可能出现较大数值差分矩阵就直接用long long。多占用一倍内存换掉一整个排查溢出的夜晚非常划算。6.3 所有add操作结束之后再做前缀和还原二维差分是离线算法它假设所有修改都已知并在最后一次性计算最终结果。如果在add操作之间穿插前缀和还原或者边修改边查询得到的结果都是错误的。我之前见过有人写出这样的代码每次add之后马上build一次结果发现后面add对前面build的影响完全乱套。正确写法永远是先积攒完所有差分标记最后再统一build。6.4 调试技巧随机小数据对拍二维差分代码调试最快的办法不是肉眼盯而是写一个对拍程序用暴力做法和差分做法同时跑随机小数据对比结果是否一致。具体做法是生成一个小的n和m比如5×5。随机生成几十次矩形更新操作。暴力做法直接用双重循环遍历矩形区域逐个加值。差分做法调用add和build得到结果。对比两个结果矩阵一旦不一致马上能定位是标记写错了还是前缀和写错了。这个习惯我保留了很久。无论一次算法写得多自信跑一遍随机对拍正确性才有底。7. 向三维差分与在线查询扩展的思路二维差分背后是一套通用的“用差分标记代替区域修改”的思维框架理解透了可以往更多方向扩展。7.1 三维差分的思路三维空间里如果要对一个长方体区域批量加v需要8个标记点分布在长方体的8个外角上。符号的规律是在8个顶点中根据该顶点相对于长方体各维度的“开始/结束”状态确定取还是-。本质上就是三维容斥和一维、二维差分的推导方式完全一致。三维差分我实际用得不多因为三维矩阵的内存开销往往很大。但遇到体积覆盖计数的问题时它能O(1)完成一次长方体修改最后O(n×m×l)还原思路值得掌握。7.2 在线场景下需要二维树状数组如果业务要求“边修改边查询某个位置的当前值”二维差分就彻底不够用了因为它必须等所有修改结束后才能一次性还原。这种在线场景需要二维树状数组Fenwick Tree配合范围修改、单点查询技巧。做法是把add操作的四个标记点改成对二维树状数组做单点更新查询某个位置的值时对(0,0)到(i,j)做一次二维前缀和查询。这样修改和查询都是O(log n × log m)可以支持实时的矩形加值和单点查询。7.3 什么时候不该硬上二维差分二维差分不是万能药遇到下面这些情况别硬用矩形个数很少矩阵也很小暴力循环完全够用。操作过程中需要频繁查询中间结果属于在线问题应该用树状数组或线段树。修改操作非常多但矩阵尺寸极大差分矩阵的内存已经扛不住需要先离线收集标记点并按坐标处理。矩形不是轴对齐的而是任意多边形差分方案就不适用了得想别的办法。我个人的体会是二维差分数组真正的甜点区间是“离线、批量、规模大”这三者同时满足的场景。判断一个算法是不是合适先看约束条件再看复杂度最后才看代码实现难度。算法本身不复杂能把它的适用范围和边界条件讲清楚才算真正掌握。 
长河君 · 2026/9/13 12:31:43 · 阅读 1.2k 二维差分数组详解：从原理到应用，高效解决矩形批量加值问题
前阵子处理一个数据统计需求时遇到了一个很典型的场景一张1000×1000的网格图要在上面叠加几十万个矩形区域的权重最后输出每个格子的最终数值。第一版用暴力循环遍历每个矩形覆盖到的格子数据量一大完全跑不动后来换成二维差分数组同样的任务从分钟级降到了毫秒级。如果你也遇到过“给矩阵的某个矩形区域批量加值最后一次性查询每个位置的值”这类问题那这篇文章正好对路。二维差分数组的原理并不复杂它是二维前缀和的逆运算专门解决“多次矩形整体修改 最终统一查询”的离线场景。竞赛选手刷区域覆盖题会用到做数据统计、图像处理的工程里同样能用上。下面我把它的原理推导、代码模板、性能对比、边界坑位一次讲清楚。1. 需求来源给矩形区域批量加值到底难在哪先别急着看公式我们从问题本身出发。假设有一张n行m列的矩阵初始全为0。现在要执行q次操作每次操作把一个子矩形区域内的所有格子加上同一个数值v比如把第2行到第5行、第3列到第7列这个矩形区域全部加3。所有操作完成后需要得到矩阵中每个位置最终的数值。1.1 一个具体的需求网格区域加权统计我当时的业务场景是线下活动的区域热力统计把一个会场划分成网格每场活动会占用一个矩形区域要给这个区域内的每个格子增加一次覆盖次数。几十万场活动标记完之后最终要输出整张会场的覆盖热力图。再举个例子图像处理里如果要把多个矩形区域的亮度同时提高也是同一类操作每个像素点就是一个格子矩形ROI区域就是待修改的区块。这类问题有一个共同特征操作次数多、矩阵规模大、但查询只在最后发生一次。如果直接用暴力做法一次矩形更新的代价是(x2 - x1 1) * (y2 - y1 1)也就是矩形面积。当矩形个数多、面积又大的时候总操作量会迅速膨胀到不可接受。1000×1000的网格50万个平均面积为10000的大矩形暴力算下来就是50亿次操作基本告别“实时出结果”这件事了。1.2 一维差分先立个样板二维差分的前身是一维差分建议在理解二维之前先把一维模型彻底吃透。一维数组a长度n要进行m次区间操作每次把[l, r]内的元素全部加上v。暴力做法是遍历l到r逐个加v一次操作O(n)。差分做法的核心是构造一个差分数组d让区间加法变成对d的常数次修改d[l] v; d[r 1] - v;所有区间操作完成后对d从头到尾做一次前缀和就能还原出每个位置被加了多少for (int i 1; i n; i) { d[i] d[i - 1]; a[i] d[i]; }这里的直觉可以这样理解d[l] v表示从位置l开始后续所有前缀和结果都会多出一个v而d[r1] - v表示累加到r1时v的影响被抵消所以真正被影响到的只有闭区间[l, r]。我以前带新人时发现很多人对一维差分里“为什么要在r1处减掉v”有点懵。其实只要对比前缀和的累加过程就明白了前缀和是带记忆的它会把之前所有差分值一路带下去所以“开始加”和“结束减”这两个标记之间的距离就是区间覆盖的范围。1.3 从“区间”到“矩形”的维度跳跃一维差分解决的是线段上的区间覆盖二维差分解决的是平面上的矩形覆盖。核心思想完全一样把“对一个区域的整体修改”转化为“对几个特殊点的修改”最后通过一次前缀和把影响扩散出去。一维区间有两个端点所以是“起点加、终点后一个位置减”两个标记。二维矩形有四个角对应的标记操作从2个变成了4个。这个跳跃在数学上是自然的——二维前缀和本身就是两个维度上的累计所以反向构造差分时也需要在两个维度上分别做“开始”和“结束”的标记。2. 四个标记点怎么来的从二维前缀和反推差分公式差分是前缀和的逆运算。想理解二维差分的四个标记点必须先看懂二维前缀和是怎么算的。2.1 二维前缀和的累加规则给定一个矩阵A它的二维前缀和S定义为S[i][j]表示从(1,1)到(i,j)这个子矩阵内所有元素的和。递推公式是S[i][j] A[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1]这个公式用到了容斥原理S[i-1][j]覆盖了上方区域S[i][j-1]覆盖了左方区域两者相加后S[i-1][j-1]这块左上角区域被算了两次所以要减掉一次。如果你想把S还原成A公式就是A[i][j] S[i][j] - S[i-1][j] - S[i][j-1] S[i-1][j-1]这是二维前缀和的逆运算。而二维差分的构造思路正好反过来我们已知每个位置的增量想找出一个差分矩阵D使得对D做二维前缀和之后得到这个增量矩阵。2.2 从约束条件反推差分标记公式假设我们希望在子矩阵(x1, y1)到(x2, y2)内的每个位置增加v。对D做二维前缀和时D中某个位置的值会向“右下方”的所有位置传播。为了精确控制传播范围我们在四个关键位置打上标记D[x1][y1] v D[x1][y21] - v D[x21][y1] - v D[x21][y21] v第一眼看上去这个“ - - ”的符号分布有点反直觉。我换个角度解释一下。前缀和的传播方向是向右下。在D[x1][y1]加v所有行坐标大于等于x1、列坐标大于等于y1的位置都会收到这个v。但这远远超出了目标矩形所以需要把它拦腰截断。在D[x21][y1]减掉v等于告诉前缀和“从x21这一行开始之前那个v的影响要终止”。但是这一减会把x21行往右的所有列也一起减掉包括目标矩形右侧下方那些本来不该受影响的位置。于是还需要在D[x1][y21]减掉v把y21列右侧的影响终止。现在目标矩形的右下方区域同时被这两个减法影响了从(x21, y1)进来的减法和从(x1, y21)进来的减法在(x21, y21)的右下方重叠等于被多减了一次。为了纠正这个重叠区域的偏差最后在D[x21][y21]加回v。所以“ - - ”的本质是两次一维截断的交叉区域修正和二维前缀和公式里的容斥是同一套逻辑。我建议你拿一张方格纸手工画一个4×4的矩阵在(2,2)到(3,3)这个矩形上做一次标记然后逐格做前缀和亲眼看一下四个标记点如何约束传播范围。这个手动推演比背公式可靠得多。2.3 直观记忆把矩形看成两组一维区间还有另一个记忆方式矩形的行区间是[x1, x2]列区间是[y1, y2]。把二维差分看作“先处理行的差分再处理列的差分”。如果只从行的维度看x1行要“开始”x21行要“结束”从列的维度看y1列要“开始”y21列要“结束”。四个角就是两个维度上“开始/结束”的四种组合。组合符号由“开始”计为、“结束”计为-决定(x1,y1)是(x1,y21)是-(x21,y1)是-(x21,y21)是。这个记忆法在扩展到三维时同样受用后面第七章会提到。3. 完整实现add操作与一次前缀和还原理论推导完了直接上代码。下面是我在实际工程和竞赛里都在用的模板按1-based下标编写也就是矩阵的行列从1开始编号。3.1 C实现模板#include bits/stdc.h using namespace std; using ll long long; const int MAXN 1005; ll diff[MAXN][MAXN]; int n, m; // 矩阵行数、列数 // 子矩阵 (x1,y1) 到 (x2,y2) 内所有格子的值增加 v void add(int x1, int y1, int x2, int y2, ll v) { diff[x1][y1] v; diff[x1][y2 1] - v; diff[x2 1][y1] - v; diff[x2 1][y2 1] v; } // 所有add操作完成后对diff做二维前缀和原地还原增量矩阵 void build() { 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]; } } }注意build()里是在原数组上原地做前缀和结果直接存在diff里。这里的diff下标从1开始第0行第0列保持为0是为了让diff[i-1][j]在边界时不会越界访问。3.2 Python版本与下标习惯如果你用Python刷题或做数据分析核心逻辑完全一样def add(x1, y1, x2, y2, v): diff[x1][y1] v diff[x1][y2 1] - v diff[x2 1][y1] - v diff[x2 1][y2 1] v def build(): for i in range(1, n 1): for j in range(1, m 1): diff[i][j] diff[i - 1][j] diff[i][j - 1] - diff[i - 1][j - 1]Python里要注意的是diff矩阵建议初始化为(n 2) * (m 2)大小的二维列表避免add操作访问到x21或y21时出现IndexError。3.3 手算验证一个4×4的小例子空口无凭我带你推一遍。有一个4×4的矩阵初始全0。现在执行一次操作把(2,2)到(3,3)这个2×2的子矩阵全部加1。add操作之后diff矩阵的非零位置如下第2行第2列1 第2行第4列-1 第4行第2列-1 第4行第4列1然后对diff做二维前缀和得到的增量矩阵应该是0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0如果加一个耗时操作比如add(1,1,2,2,1)和add(2,2,3,3,2)叠加最终还原出来的矩阵会是什么留给你自己动手跑一下。这是检验自己是否真正理解二维差分最直接的方式手动推演两个矩形重叠的标记和还原结果全程不碰代码。3.4 原矩阵有初始值时的处理方式上面讲的模板假设初始矩阵全为0差分矩阵记录的纯粹是增量。如果原矩阵本身有数值有两种处理思路。第一种最简单也最不容易出错差分矩阵只记录增量最后把原始矩阵和增量矩阵相加for (int i 1; i n; i) for (int j 1; j m; j) ans[i][j] base[i][j] diff[i][j];第二种把原始矩阵也看作“点更新”的叠加即对每个base[i][j]执行一次“单点加”的差分标记。单点加本身就是把矩形退化成(i,j)到(i,j)的特例四个标记点都落在同一个顶点上。但这样会让add操作数量变成n*m q当矩阵很大时反而更慢。我个人的建议是不要玩花活直接方案一。多开一个矩阵不会让内存压力大到哪去但逻辑清晰度提升是实打实的。4. 复杂度与性能边界这个算法的收益到底有多大二维差分数组的复杂度分析很简单但很多人没意识到它真正的优势区间在哪里。4.1 暴力、差分的复杂度拆解暴力做法每次矩形更新遍历区域内所有格子单次成本是(x2-x11)*(y2-y11)最坏情况下等于整个矩阵面积n*m。q次操作后总复杂度是O(q*n*m)。二维差分做法每次矩形更新只做常数次数组加减单次成本O(1)。所有操作完成后做一次二维前缀和成本是O(n*m)。总复杂度是O(q n*m)。关键区别在于暴力里q和n*m是相乘的关系差分里它们是相加的关系。当q和矩阵面积都很大时这个差距是指数级的。4.2 实际数据对比我专门写了个脚本测试n1000, m1000执行10万次随机矩形加值操作的耗时对比方案时间复杂度1000×1000矩阵、10万次更新的估算耗时暴力遍历矩形O(q × 矩形面积)最坏约1e11次加法分钟级以上二维差分O(q n×m)约1.4e6次运算毫秒级1e11次加法是什么概念普通CPU一秒钟大概能跑几亿次简单整数运算1e11次加法理论耗时也得几十秒到几分钟。而差分方案里10万次矩形更新的标记操作只有40万次加减加上100万次的二维前缀和还原总共140万次运算一毫秒到几毫秒就能跑完。4.3 内存与优化思路差分矩阵需要(n2)*(m2)的空间。如果矩阵是1000×1000用long long存储大约8MB完全可以接受。但如果矩阵尺寸达到1万×1万差分矩阵需要400MB以上这就有点紧张了需要考虑更节省内存的方案。内存吃紧时有一个思路如果矩形个数相对较少可以先把所有add操作的四个标记点离线存下来按坐标排序后统一累加避免开完整的差分矩阵。这种做法适合矩阵巨大但操作数较少的场景属于用时间换空间。不过大多数情况下直接开差分矩阵就够了不必过度优化。5. 三个典型应用场景刷题、业务统计与图像处理原理和实现都聊完了看几个实际用得上二维差分的场景。5.1 竞赛场景区域覆盖计数算法题里最常见的考法就是“给你一堆矩形求每个格子被覆盖了多少次”。比如碰到的这类题一个n×n的网格输入m个矩形的左上角和右下角坐标每个矩形覆盖到的格子计数加1最后输出整个网格的覆盖情况。这类题用二维差分几乎是送分题。每次给一个矩形做add操作最后build一次再输出每个格子的值就行了。我建议第一次接触二维差分的人找一两道这样的简单题作为练手入口重点不是为了AC而是验证自己对四个标记点的理解是否到位。5.2 业务统计线下活动的区域加权回到开头提到的会场热力统计。每场活动占用一个矩形区域要统计每个展位的覆盖次数。用二维差分每场活动只记录四次标记最后统一还原几十万场活动的数据量也能轻松处理。这类离线批量统计场景非常契合二维差分的特性操作量大、中间不查询、只在最后做一次总量计算。如果业务中还需要“边更新边查询”二维差分就不够用了后面第七章会展开说。5.3 图像处理多个ROI区域批量增强图像本质上就是一个二维矩阵。要对多个矩形ROI区域做灰度增强可以先用二维差分记录每个像素点的亮度增量最后一次性叠加到原图上。相比逐像素循环处理差分方案会让整体计算链路简洁很多尤其是在ROI数量多、区域面积大的情况下。需要注意的是图像处理中的常见坐标系以左上角为原点行列都是从0开始编号。用差分时要处理好下标偏移确保add操作访问的下标都在数组范围内。6. 最容易翻车的边界与调试经验二维差分的代码量很少但正因为代码量少出错了反而不容易一眼看出问题。下面几个坑是我自己踩过也看别人踩过无数次的。6.1 数组一定要多开一圈add操作里会出现x2 1和y2 1。如果x2恰好等于矩阵最后一行n那么就要访问diff[n1][...]这一行。所以数组至少需要(n2)*(m2)大小不能只开到(n1)*(m1)更不能只开到n*m。我之前用C写题时数组开成MAXN][MAXN]但MAXN只比n大1结果add访问到diff[n1]时越界程序行为完全随机。这类越界问题在本地小数据时可能不触发数据一大就崩。养成习惯凡是处理差分数组无脑多开两格省去排查越界的时间。6.2 用long long防止溢出如果每次加的值v很大、操作次数q很多单个格子的最终值可能远超int范围。比如1000×1000矩阵50万次操作每次加10000理论上一个格子可能被所有操作覆盖最终值达到50亿已经超过int的21.47亿上限。所以只要v和q可能出现较大数值差分矩阵就直接用long long。多占用一倍内存换掉一整个排查溢出的夜晚非常划算。6.3 所有add操作结束之后再做前缀和还原二维差分是离线算法它假设所有修改都已知并在最后一次性计算最终结果。如果在add操作之间穿插前缀和还原或者边修改边查询得到的结果都是错误的。我之前见过有人写出这样的代码每次add之后马上build一次结果发现后面add对前面build的影响完全乱套。正确写法永远是先积攒完所有差分标记最后再统一build。6.4 调试技巧随机小数据对拍二维差分代码调试最快的办法不是肉眼盯而是写一个对拍程序用暴力做法和差分做法同时跑随机小数据对比结果是否一致。具体做法是生成一个小的n和m比如5×5。随机生成几十次矩形更新操作。暴力做法直接用双重循环遍历矩形区域逐个加值。差分做法调用add和build得到结果。对比两个结果矩阵一旦不一致马上能定位是标记写错了还是前缀和写错了。这个习惯我保留了很久。无论一次算法写得多自信跑一遍随机对拍正确性才有底。7. 向三维差分与在线查询扩展的思路二维差分背后是一套通用的“用差分标记代替区域修改”的思维框架理解透了可以往更多方向扩展。7.1 三维差分的思路三维空间里如果要对一个长方体区域批量加v需要8个标记点分布在长方体的8个外角上。符号的规律是在8个顶点中根据该顶点相对于长方体各维度的“开始/结束”状态确定取还是-。本质上就是三维容斥和一维、二维差分的推导方式完全一致。三维差分我实际用得不多因为三维矩阵的内存开销往往很大。但遇到体积覆盖计数的问题时它能O(1)完成一次长方体修改最后O(n×m×l)还原思路值得掌握。7.2 在线场景下需要二维树状数组如果业务要求“边修改边查询某个位置的当前值”二维差分就彻底不够用了因为它必须等所有修改结束后才能一次性还原。这种在线场景需要二维树状数组Fenwick Tree配合范围修改、单点查询技巧。做法是把add操作的四个标记点改成对二维树状数组做单点更新查询某个位置的值时对(0,0)到(i,j)做一次二维前缀和查询。这样修改和查询都是O(log n × log m)可以支持实时的矩形加值和单点查询。7.3 什么时候不该硬上二维差分二维差分不是万能药遇到下面这些情况别硬用矩形个数很少矩阵也很小暴力循环完全够用。操作过程中需要频繁查询中间结果属于在线问题应该用树状数组或线段树。修改操作非常多但矩阵尺寸极大差分矩阵的内存已经扛不住需要先离线收集标记点并按坐标处理。矩形不是轴对齐的而是任意多边形差分方案就不适用了得想别的办法。我个人的体会是二维差分数组真正的甜点区间是“离线、批量、规模大”这三者同时满足的场景。判断一个算法是不是合适先看约束条件再看复杂度最后才看代码实现难度。算法本身不复杂能把它的适用范围和边界条件讲清楚才算真正掌握。