二维差分怎么做？如何 O(1) 给一个子矩阵批量加值？

简化版

二维差分把一维差分推广到矩阵,用于「多次给子矩阵批量加值、最后统一查询」。给子矩阵 (r1,c1) 到 (r2,c2) 每个元素加 val,只需在差分矩阵的四个角做修改:diff[r1][c1] += val、diff[r1][c2+1] -= val、diff[r2+1][c1] -= val、diff[r2+1][c2+1] += val,O(1)。所有操作后对差分矩阵求二维前缀和还原。把 m 次子矩阵更新从 O(mnq) 降到 O(mn + q) 级。

详细版

// 给子矩阵 (r1,c1)~(r2,c2) 每个元素加 val，O(1)，四个角操作
void rangeAdd2D(int[][] diff, int r1, int c1, int r2, int c2, int val) {
    diff[r1][c1]       += val;   // 左上角，开始加
    diff[r1][c2 + 1]   -= val;   // 右边界外，抵消右侧
    diff[r2 + 1][c1]   -= val;   // 下边界外，抵消下方
    diff[r2 + 1][c2+1] += val;   // 右下角外，加回被减两次的部分（容斥）
}

// 所有操作后，二维前缀和还原
void restore(int[][] diff, int m, int n) {
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (i > 0) diff[i][j] += diff[i-1][j];
            if (j > 0) diff[i][j] += diff[i][j-1];
            if (i > 0 && j > 0) diff[i][j] -= diff[i-1][j-1];
        }
    // 此时 diff 就是加完值的结果矩阵
}

完整版教学

一、从一维差分到二维差分

一维差分给区间加 val,用「左端点 +val、右端点后 -val」两个操作限定影响范围。二维差分同理,但因为是矩形,要用四个角的容斥来精确框住子矩阵。核心思想不变:在差分矩阵上做几个 O(1) 的角点修改,最后用二维前缀和一次性还原——前缀和的过程会把这些角点的影响「扩散」成整个子矩阵的加法。

二、四个角的容斥(重点)

给子矩阵 (r1,c1)~(r2,c2) 加 val,要在差分矩阵四个位置操作:

diff[r1][c1]     += val    // ① 从左上角起，向右下所有区域 +val
diff[r1][c2+1]   -= val    // ② 抵消掉「c2 右边」多加的部分
diff[r2+1][c1]   -= val    // ③ 抵消掉「r2 下边」多加的部分
diff[r2+1][c2+1] += val    // ④ ②③重复减了右下角一块，加回来

理解方式:diff[r1][c1] += val 相当于「给以 (r1,c1) 为左上角、一直到矩阵右下角的整个大区域加 val」。这会溢出目标子矩阵,所以用 ②③ 减掉右边和下边溢出的部分;而 ②③ 把右下角那块减了两次,再用 ④ 加回来。这是和二维前缀和查询完全对称的容斥。

三、为什么最后用二维前缀和还原

四个角的修改只是在差分矩阵上「埋点」,真正的加法效果要靠二维前缀和「显影」。因为二维差分和二维前缀和互逆:对差分矩阵求二维前缀和,每个角点的 ±val 会沿着「向右下累加」的方向扩散,①的 +val 铺满右下大区域,②③④ 的修正正好把它裁剪成目标子矩阵。还原公式就是标准的二维前缀和:diff[i][j] += 上 + 左 - 左上。

四、下标越界的处理

四个角里有 c2+1 和 r2+1,当子矩阵贴着矩阵右边界/下边界时会越界。处理办法:把差分矩阵开成 (m+1)×(n+1) 或 (m+2)×(n+2),多留出边界,让 r2+1、c2+1 有地方落脚(那些越界的修正落在填充区,不影响最终结果区)。这是二维差分实现时必须注意的边界细节。

五、复杂度与适用场景

每次子矩阵加:O(1)(四个角)。
最后还原:O(mn)(二维前缀和)。
总计:q 次更新 + 一次还原 = O(q + mn),而朴素做法每次更新遍历子矩阵是 O(q·mn)。
适用:大量「给某个矩形区域加值」的操作,最后才看每个格子的值。如:
- 图像/网格的区域批量染色/加权。
- 地图上多个矩形区域叠加影响(信号覆盖、热力叠加)。
- 航班/预订的二维版本。

和一维差分一样,适合「批量更新在前、查询在后」;更新查询交替则用二维树状数组/线段树。

六、和二维前缀和的对称关系

二维前缀和(查子矩阵和)和二维差分(给子矩阵加值)是互逆的一对,连容斥公式的形状都对称:

二维前缀和查询:P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1](大矩形 - 上条 - 左条 + 左上)。
二维差分更新:diff[r1][c1] += v, diff[r1][c2+1] -= v, diff[r2+1][c1] -= v, diff[r2+1][c2+1] += v(四角容斥)。

一个管「区间查」、一个管「区间改」,都靠容斥,是二维版的「前缀和/差分」对偶。

七、从公式证明到手算闭环

这道题成立的核心是：矩形更新通过四角标记控制二维前缀传播：左上开启，右侧与下侧关闭，右下补偿重复关闭。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

add(x1,y1,x2,y2,v):
d[x1][y1] += v
d[x1][y2+1] -= v
d[x2+1][y1] -= v
d[x2+1][y2+1] += v

带数字推演：在 3×3 零矩阵的 (0,0)-(1,1) 加 5，四角记为 +5,-5,-5,+5，二维累加后只有左上 2×2 为 5。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	矩形更新通过四角标记控制二维前缀传播：左上开启，右侧与下侧关闭，右下补偿重复关闭
复杂度	每次矩形更新 O(1)，统一还原 O(mn)，额外空间 O(mn)
关键边界	可开 `(m+1)×(n+1)` 或 `(m+2)×(n+2)` 哨兵矩阵避免每次判界；还原必须做二维前缀和而非逐行累加

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：可开 (m+1)×(n+1) 或 (m+2)×(n+2) 哨兵矩阵避免每次判界；还原必须做二维前缀和而非逐行累加。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：二维差分只改左上和右下两个角。 还需要右上、左下关闭横纵传播。
误区：四角符号都是一正一负随便放。 符号由二维容斥唯一决定：+ - - +。
误区：逐行前缀即可恢复。 还需纵向累计，否则影响无法扩散到后续行。
追问：右下角为何再加 v？ 右侧和下侧各减一次，交叉区域被减两次，需要补回一次。
追问：在线矩形更新与查询怎么办？ 选择二维树状数组或二维线段树，并评估内存。
追问：怎样降低越界判断复杂度？ 额外分配哨兵行列，让 x2+1、y2+1 始终合法。

十、加强记忆

二维差分给子矩阵 (r1,c1)~(r2,c2) 加 val,只改四个角:diff[r1][c1]+=val、diff[r1][c2+1]-=val、diff[r2+1][c1]-=val、diff[r2+1][c2+1]+=val(容斥:左上起铺满,减右溢下溢,加回重复减的右下),O(1)。所有操作后二维前缀和还原。总 O(q+mn)(朴素 O(q·mn))。差分矩阵要多开一圈防 r2+1/c2+1 越界。它和二维前缀和(查子矩阵和)互逆对称,一个管改、一个管查。

简化版

详细版