auto_ai 知识库

Appearance

二维差分是二维前缀和的逆运算，通过差分数组实现 O(1) 时间内对任意子矩阵进行区间加减操作。适用于大量子矩阵区间修改、最后统一查询的场景，是二维前缀和的"镜像"技术。

定义与核心原理 ​

设原矩阵为 a[i][j]，差分数组为 d[i][j]。二维差分的核心思想是：对子矩阵 (x1,y1)~(x2,y2) 统一加上 val，只需在差分数组的四个角做标记，最后求一次前缀和即可完成全部修改。

区间修改公式 ​

对以 (x1,y1) 为左上角、(x2,y2) 为右下角的子矩阵全部加 val：

d[x1][y1]         += val
d[x1][y2+1]       -= val
d[x2+1][y1]       -= val
d[x2+1][y2+1]     += val

图解（四个标记点） ​

(x1,y1) ──────── (x1,y2+1)
  │ +val             │ -val
  │                  │
(x2+1,y1) ────── (x2+1,y2+1)
  │ -val             │ +val

原理：对差分数组求前缀和时，+val 会向右下扩散，-val 会截断扩散范围，四个角配合恰好只影响目标子矩阵。

四步影响图解（目标子矩阵 (x1,y1)~(x2,y2) 加 c）：

步骤操作影响范围作用
1b[x1][y1] += c从 (x1,y1) 向右下全部 +c开启影响
2b[x1][y2+1] -= c从 (x1,y2+1) 向右下全部 -c截断右边界
3b[x2+1][y1] -= c从 (x2+1,y1) 向右下全部 -c截断下边界
4b[x2+1][y2+1] += c从 (x2+1,y2+1) 向右下全部 +c修正右下角（被减了两次）

最终只有 (x1,y1)~(x2,y2) 范围内的元素净增加 c，其余区域正负抵消。

操作步骤 ​

1. 初始化差分数组 ​

cpp
// 方法一：从原矩阵构建
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
    }
}

// 方法二：直接用区间添加构建（每个元素视为 1×1 子矩阵）
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        add(i, j, i, j, a[i][j]);
    }
}

2. 执行区间修改 ​

cpp
void add(int x1, int y1, int x2, int y2, int val) {
    d[x1][y1] += val;
    d[x1][y2+1] -= val;
    d[x2+1][y1] -= val;
    d[x2+1][y2+1] += val;
}

3. 求前缀和还原原矩阵 ​

cpp
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        a[i][j] = d[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
    }
}

复杂度分析 ​

操作时间复杂度说明
单次区间修改O(1)四个角标记
最终还原O(n×m)求一次前缀和
空间O(n×m)差分数组

适用场景：修改多、查询少（最后统一查询）。如果修改少查询多，用二维前缀和更合适。

实践应用 ​

  • 矩阵区域加减：多次对子矩阵加/减某个值
  • 差分矩阵模板题：如"激光炸弹"、"地毯覆盖"等经典题
  • 图像区域处理：对图像矩形区域统一调整亮度
  • 与二维前缀和配合：差分做修改，前缀和做查询

常见误区 ​

  1. 忘记 +1 边界：y2+1 和 x2+1 是关键，差分数组要开 (n+2)×(m+2) 防止越界
  2. 符号记错：左上角和右下角 +val，右上角和左下角 -val
  3. 混淆前缀和和差分：前缀和解决"查询多修改少"，差分解决"修改多查询少"

一句话总结 ​

二维差分是 二维前缀和 的逆运算：子矩阵加减只在四个角打 ±val 标记，单次修改 O(1)，最后求一次前缀和还原；适合修改多、查询少的场景。

相关概念 ​