AcWing做题笔记——差分与差分矩阵

一维差分

1. 什么是差分数组？

• 核心定义：对于一个原始数组 A，它的差分数组 B 被定义为：
  • B[i] = A[i] - A[i-1] (当 i > 1 时)
  • B[1] = A[1] (当 i = 1 时)
• 核心性质：原始数组 A 是差分数组 B 的前缀和。
  • A[i] = B[1] + B[2] + ... + B[i]
• 一句话总结：差分数组记录的是原数组中每个元素相对于前一个元素的增量。

2. 如何实现区间修改？

• 问题：给数组 A 的区间 [l, r] 内的所有元素都加上 c。
• 差分操作：我们只需要对差分数组 B 做两个点的修改：
  1. B[l] += c
  2. B[r + 1] -= c
• 原理解释：
  • B[l] += c：当通过前缀和还原 A 数组时，从 A[l] 开始的每一个元素都会受到这个 +c 的影响。
  • B[r + 1] -= c：为了抵消在 r 之后的多余影响，在 r+1 的位置减去 c。这样，从 A[r+1] 开始，+c 和 -c 的效果正好抵消，数组恢复原样。

3. 完整流程与代码

1. 构造：根据原始数组 A 构造出差分数组 B。
2. 修改：对于每一次区间 [l, r] 的修改，执行 B[l] += c 和 B[r + 1] -= c。
3. 还原：所有修改完成后，通过计算 B 的前缀和，得到最终的 A 数组。

// 推荐使用 1-based 索引，代码更清晰
#include <iostream>
#include <vector>

const int N = 100010;
int a[N], b[N];

// 修改函数
void update(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

int main() {
    int n, m; // 数组长度，操作次数
    std::cin >> n >> m;

    // 构造：通过 n 次单点修改来构建差分数组
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        update(i, i, a[i]);
    }

    // 修改
    while (m--) {
        int l, r, c;
        std::cin >> l >> r >> c;
        update(l, r, c);
    }

    // 还原：通过前缀和计算最终的 a 数组
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1]; // b[i] 现在存储的是 a[i] 的最终值
        std::cout << b[i] << ' ';
    }
    return 0;
}

---

二维差分矩阵

1. 什么是差分矩阵？

• 核心定义：对于原始矩阵 A，其差分矩阵 B 满足：
  • B[i][j] = A[i][j] - A[i-1][j] - A[i][j-1] + A[i-1][j-1]
• 这个咋来的：你反过来就是
  • A[i][j]=A[i−1][j]+A[i][j−1]−A[i−1][j−1]+B[i][j]
  • 就是求二维前缀和的过程
• 核心性质：原始矩阵 A 是差分矩阵 B 的二维前缀和。
• 一句话总结：差分矩阵记录的是原矩阵中某点相对于其上方和左方区域影响的纯粹增量。

2. 如何实现子矩阵修改？

• 问题：给以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵所有元素加上 c。
• 差分操作（容斥原理的应用）：只需要修改差分矩阵 B 的四个点：
  1. B[x1][y1] += c
  2. B[x1][y2 + 1] -= c
  3. B[x2 + 1][y1] -= c
  4. B[x2 + 1][y2 + 1] += c
• 原理解释（可以配图说明）：
  1. 在 (x1, y1) 加上 c，让右下角整个区域生效。
  2. 在 (x1, y2 + 1) 减去 c，抵消掉目标区域右边的多余影响。
  3. 在 (x2 + 1, y1) 减去 c，抵消掉目标区域下方的多余影响。
  4. 在 (x2 + 1, y2 + 1) 加上 c，补偿因为第2、3步导致被重复减去的右下角区域。

3. 完整流程与代码

1. 构造：基于原始矩阵 A 构造差分矩阵 B。
2. 修改：对每一次子矩阵修改，执行上述四点操作。
3. 还原：通过计算 B 的二维前缀和，得到最终的 A 矩阵。

#include <iostream>

const int N = 1010;
int a[N][N], b[N][N];

// 修改函数
void update(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    int n, m, q; // 行，列，操作次数
    std::cin >> n >> m >> q;

    // 构造
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> a[i][j];
            update(i, j, i, j, a[i][j]);
        }
    }

    // 修改
    while (q--) {
        int x1, y1, x2, y2, c;
        std::cin >> x1 >> y1 >> x2 >> y2 >> c;
        update(x1, y1, x2, y2, c);
    }
    
    // 还原
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            std::cout << b[i][j] << ' ';
        }
        std::cout << '\n';
    }
    return 0;
}