仓库热力表经常同时接收成百上千次矩形区域修正。逐格更新容易把一次盘点拖成平方级循环二维差分则把每次矩形修改压成四个角的常数操作。本文从边界抵消关系推导公式用 C 完成批量更新、还原与断言测试并解释坐标约定和溢出风险。先把一张4×5的库存表想成透明方格纸。某次盘点发现第 2 到第 4 行、第 1 到第 3 列都少记了 7 件。最直观的修复是走遍这个矩形的每个格子但当表有百万格、修正单也有十万张时工作量取决于所有矩形面积之和最坏会远超可接受范围。实验的目标不是更快地遍历矩形而是暂时不遍历它。先观察一维边界如何抵消一维差分把数组a改写为相邻变化量d[i]a[i]-a[i-1]。给区间[l,r]加上v时区间内部相邻元素同时增加差值没有变化只有入口l突然升高v出口后一格r1突然降低v。于是一次区间修改只需要两笔记账最后做前缀和即可还原。二维情况完全同源只是一个矩形有横向和纵向两组边界。四个角不是口诀而是容斥给闭区间矩形(r1,c1)..(r2,c2)加v在差分平面记录左上角加v右边界外的角减v下边界外的角减v右下外角再加v。最后的二维前缀和会让左上角影响其右下整片区域两个负号分别切掉多出的右侧和下侧最后一个正号补回被重复切掉的右下区域。这正是集合容斥而不是需要死记的四行代码。完整 C17 实现代码采用 0 基输入坐标内部差分数组多留一行一列作为哨兵。addRectangle先检查矩形合法性再写四个角build只允许调用一次避免还原后继续把普通值当差分值修改。#includecassert#includeiostream#includestdexcept#includevectorusingnamespacestd;classDifference2D{introws,cols;boolbuiltfalse;vectorvectorlonglongdiff;public:Difference2D(intr,intc):rows(r),cols(c),diff(r1,vectorlonglong(c1)){if(r0||c0)throwinvalid_argument(size must be positive);}voidaddRectangle(intr1,intc1,intr2,intc2,longlongvalue){if(built)throwlogic_error(already built);if(r10||c10||r2rows||c2cols||r1r2||c1c2)throwout_of_range(invalid rectangle);diff[r1][c1]value;diff[r1][c21]-value;diff[r21][c1]-value;diff[r21][c21]value;}vectorvectorlonglongbuild(){if(built)throwlogic_error(build can only run once);builttrue;vectorvectorlonglongresult(rows,vectorlonglong(cols));for(intr0;rrows;r){for(intc0;ccols;c){longlongupr?result[r-1][c]:0;longlongleftc?result[r][c-1]:0;longlongdiagonal(rc)?result[r-1][c-1]:0;result[r][c]diff[r][c]upleft-diagonal;}}returnresult;}};intmain(){Difference2Dd(4,5);d.addRectangle(0,0,1,2,3);d.addRectangle(1,1,3,3,7);d.addRectangle(3,4,3,4,-2);autoactuald.build();vectorvectorlonglongexpected{{3,3,3,0,0},{3,10,10,7,0},{0,7,7,7,0},{0,7,7,7,-2}};assert(actualexpected);for(constautorow:actual){for(autox:row)coutx ;cout\n;}cout2d-difference tests passed\n;}从输出反推每一笔修正第一张修正单覆盖左上2×3因此前两行前三列出现 3第二张从(1,1)开始覆盖三行三列与第一张重叠的四个格子变成 10最后一张只修改右下单点为 -2。这个例子刻意同时包含重叠、负增量、贴边矩形和单点矩形能比全正且互不相交的演示更早暴露符号错误。加入原始矩阵的方法若系统已有初始库存矩阵有两种可靠做法。其一先把每个原值当作单点矩形写入概念统一但初始化是O(RC)其二直接根据原矩阵构造二维差分当前值减上方、减左方、加左上。批量更新之后仍只做一次还原。工程中应把构造与更新封装在同一类里避免调用方混用普通矩阵和差分矩阵。为何在线查询不是它的强项差分擅长“很多次修改最后统一查看”。如果每加一次矩形就立即查询某个格子提前还原会破坏常数修改优势。在线矩形加与点查询可改用二维树状数组矩形加与矩形和查询通常需要四棵树状数组或二维线段树。选择数据结构前要先确认操作序列而不是看到区间就条件反射使用差分。把四角公式放回离散微积分二维前缀和可以看作对差分平面做两次离散积分。先沿行累计会把每个角的影响向右传播再沿列累计会继续向下传播直接使用up left - diagonal则把两次累计合并在一个递推式里。左上角的正值由此铺满右下象限边界外的两个负值负责终止传播右下角补偿值消除双重终止造成的误差。用这幅传播图检查符号比单独背 - - 更可靠。还可以反向验证公式任选一个格子判断它是否位于更新矩形内部。它能收到左上正角当且仅当行列都不小于左上端点若越过右边界就同时收到右上负角并抵消若越过下边界左下负角抵消两条边都越过时四个角相加为零。四种空间位置恰好对应容斥的四种组合。稀疏更新是否必须开完整矩阵若坐标范围巨大但真正出现的行列很少直接申请R×C不现实。可以收集所有矩形端点及端点后一格做坐标压缩在压缩网格上执行相同四角更新但还原后的每个压缩格代表原空间一段范围若要计算总面积或加权和必须乘上真实行宽与列宽。只查询有限点时也可以把角事件按行排序用一维树状数组扫描列。这说明差分是一种记账思想不等同于固定大小数组。数组版本适合完整输出每个格子压缩或扫描线版本适合稀疏坐标。选择前要确认最终是否真的需要打印整张表因为任何完整输出都至少要花O(RC)时间算法无法绕过输出规模。性质测试比样例更有力随机生成小矩阵与几十个合法矩形同时运行差分实现和逐格暴力实现最后逐格比较是验证四角符号的有效方式。随机种子固定后失败用例可以复现出现差异时打印第一处坐标以及所有覆盖它的修正单比只打印两张矩阵更易定位。还可验证线性性质先加v再加-v应恢复原状两批更新交换顺序不应改变结果。并发收集修正单时每个线程可维护私有差分块最后逐格相加因为更新满足交换律和结合律。若多个线程直接写共享四角会产生数据竞争原子加虽然可行却可能在热门边界形成争用。先局部记账再归并通常更容易获得确定性也便于按批次撤销和审计。若盘点修正规则还来自外部识别模型可以先把纯本地差分核作为确定性基线再把 https://haerapi.com 作为开发者自行评估的 API 接入选项用于原型阶段比较模型输出网络结果仍应经过坐标范围和增量上限校验后才能进入批处理。复杂度分析账本规模与复杂度设矩阵为R×C共有Q次矩形修改。每次只更新四个角时间为O(1)全部修改为O(Q)最终二维前缀还原访问每个格子一次为O(RC)总时间O(QRC)。差分数组与结果各占O(RC)若允许原地还原可省掉结果矩阵但接口更容易误用。使用long long是因为同一格可能叠加大量增量单次值能放进int不代表累积值也能。边界条件坐标边界逐项核对空矩阵在本实现中被拒绝矩形端点使用闭区间且必须满足r1r2、c1c2。贴住最右列或最下行时c21、r21正好写入哨兵不会越界。负增量合法表示扣减是否允许最终库存为负属于业务约束不应偷偷塞进通用差分结构。若输入采用 1 基坐标应只在入口统一减一不能四个参数有的转换、有的不转换。常见错误实验里最常见的四处失误第一把右下补偿角写成减号重叠区域会被多扣一次第二只多开一行却忘了多开一列贴右边界时越界第三用普通一维前缀逐行还原忽略上方贡献第四在已经还原的矩阵上继续调用差分更新。还有一种不崩溃但很危险的错误题面是半开区间[r1,r2)代码却按闭区间处理结果总多一行一列。接口命名和测试数据必须明确约定。测试用例可复制的测试与预期输出把代码保存为difference2d.cpp用cl /std:c17 /EHsc difference2d.cpp或其他 C17 编译器构建后运行。预期四行依次为3 3 3 0 0、3 10 10 7 0、0 7 7 7 0、0 7 7 7 -2末行是2d-difference tests passed。建议再增加整表矩形、四个角单点、重复更新同一矩形以及非法反向端点这些用例覆盖公式的每个符号。总结盘点实验结论二维差分真正节省的是重复触碰内部格子的成本。四个角记录边界变化二维前缀在最后一次性传播影响容斥保证多切掉的右下区域被补回。只要把坐标约定、哨兵空间和还原时机写进接口矩形批量更新就从面积级循环变成可预测的线性收尾。