题解 | #【模板】二维差分#

题目链接

题目描述

给定一个 $n \times m$ 的整数矩阵，初始矩阵为 $A$ 。现在需要支持 $q$ 次操作，每次操作给定五个整数 $x_1, y_1, x_2, y_2, v$ ，表示将以 $(x_1, y_1)$ 为左上角、 $(x_2, y_2)$ 为右下角的子矩阵内的每个元素都增加 $v$ 。全部操作执行完毕后，请输出最终矩阵。

解题思路

本题要求对一个二维矩阵进行多次子矩阵修改。如果每次修改都通过双重循环遍历子矩阵并更新元素，单次操作的复杂度为 $O(n \cdot m)$ ，总复杂度将达到 $O(n \cdot m \cdot q)$ ，在数据量较大时会超时。

为了高效处理区域修改，我们可以将一维差分的思想扩展到二维，使用二维差分矩阵。

1. 二维差分与二维前缀和的关系

二维差分和二维前缀和互为逆运算。如果我们将最终的矩阵 $A$ 视作一个二维前缀和矩阵，那么我们就可以通过一个“源”矩阵 $D$ （即差分矩阵）来构建它。它们的关系如下：

从差分还原前缀和: $A[i][j] = D[i][j] + A[i-1][j] + A[i][j-1] - A[i-1][j-1]$
从前缀和构建差分: $D[i][j] = A[i][j] - A[i-1][j] - A[i][j-1] + A[i-1][j-1]$

2. 二维差分如何优化区域修改？

核心思想是：对差分矩阵 $D$ 的一个点 $D[i][j]$ 加上值 $v$ ，在通过前缀和还原后，会使得原矩阵中所有右下角坐标 $(x, y)$ 满足 $x \ge i$ 且 $y \ge j$ 的元素都增加 $v$ 。这相当于对一个无限大的右下区域进行了整体修改。

利用这个性质，我们可以通过对差分矩阵的四个角点进行修改，来实现对一个有限子矩阵的修改。这个过程利用了容斥原理：要对左上角为 $(x_1, y_1)$ ，右下角为 $(x_2, y_2)$ 的子矩阵全部加上 $v$ ，我们只需对差分矩阵 $D$ 做如下四个操作：

D[x1][y1] += v：使得整个右下区域 $(x_1, y_1) \to (\infty, \infty)$ 的值都增加了 $v$ 。
D[x1][y2 + 1] -= v：为了抵消掉右边多余部分的影响，将区域 $(x_1, y_2+1) \to (\infty, \infty)$ 减去 $v$ 。
D[x2 + 1][y1] -= v：为了抵消掉下边多余部分的影响，将区域 $(x_2+1, y_1) \to (\infty, \infty)$ 减去 $v$ 。
D[x2 + 1][y2 + 1] += v：由于区域 $(x_2+1, y_2+1) \to (\infty, \infty)$ 被减了两次，需要加回来一次。

这样，一次复杂的子矩阵修改操作就被转换为了对差分矩阵的四次单点修改，时间复杂度从 $O(n \cdot m)$ 降为 $O(1)$ 。

3. 算法流程

构建初始差分矩阵：根据初始矩阵 $A$ 计算出其对应的差分矩阵 $D$ 。这一步的复杂度是 $O(n \cdot m)$ 。
处理所有修改：对于 $q$ 次操作，每次操作都只修改差分矩阵 $D$ 的四个点。这一步的复杂度是 $O(q)$ 。
还原最终矩阵：所有修改操作完成后，差分矩阵 $D$ 已经包含了初始状态和所有修改的信息。我们通过计算 $D$ 的二维前缀和，就可以还原出最终的矩阵。这一步的复杂度是 $O(n \cdot m)$ 。

总时间复杂度为 $O(n \cdot m + q)$ ，远优于朴素算法。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    // 差分矩阵，大小设为 (n+2)x(m+2) 以便处理边界
    vector<vector<LL>> d(n + 2, vector<LL>(m + 2, 0));

    // 1. 构建初始差分矩阵
    vector<vector<LL>> a(n + 1, vector<LL>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            // 计算初始差分
            d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
        }
    }

    // 2. 处理所有修改
    for (int k = 0; k < q; ++k) {
        int x1, y1, x2, y2;
        LL v;
        cin >> x1 >> y1 >> x2 >> y2 >> v;
        d[x1][y1] += v;
        d[x2 + 1][y1] -= v;
        d[x1][y2 + 1] -= v;
        d[x2 + 1][y2 + 1] += v;
    }

    // 3. 通过前缀和还原最终矩阵并输出
    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];
            cout << a[i][j] << (j == m ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();

        // 差分矩阵, 大小设为 (n+2)x(m+2) 以便处理边界
        long[][] d = new long[n + 2][m + 2];
        long[][] a = new long[n + 1][m + 1];

        // 1. 构建初始差分矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = sc.nextLong();
                d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
            }
        }

        // 2. 处理所有修改
        for (int k = 0; k < q; k++) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            long v = sc.nextLong();
            
            d[x1][y1] += v;
            d[x2 + 1][y1] -= v;
            d[x1][y2 + 1] -= v;
            d[x2 + 1][y2 + 1] += v;
        }

        // 3. 通过前缀和还原最终矩阵并输出
        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];
                System.out.print(a[i][j] + (j == m ? "" : " "));
            }
            System.out.println();
        }
    }
}

def solve():
    n, m, q = map(int, input().split())

    # 差分矩阵, 大小设为 (n+2)x(m+2)
    d = [[0] * (m + 2) for _ in range(n + 2)]
    a = [[0] * (m + 1) for _ in range(n + 1)]

    # 1. 构建初始差分矩阵
    for i in range(1, n + 1):
        row = list(map(int, input().split()))
        for j in range(1, m + 1):
            a[i][j] = row[j-1]
            d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

    # 2. 处理所有修改
    for _ in range(q):
        x1, y1, x2, y2, v = map(int, input().split())
        d[x1][y1] += v
        d[x2 + 1][y1] -= v
        d[x1][y2 + 1] -= v
        d[x2 + 1][y2 + 1] += v
        
    # 3. 通过前缀和还原最终矩阵
    final_a = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        row_list = []
        for j in range(1, m + 1):
            final_a[i][j] = d[i][j] + final_a[i-1][j] + final_a[i][j-1] - final_a[i-1][j-1]
            row_list.append(final_a[i][j])
        print(*row_list)

solve()

算法及复杂度

算法：二维差分 (2D Difference Array)
时间复杂度： $O(n \cdot m + q)$ 。其中 $O(n \cdot m)$ 用于构建初始差分矩阵和还原最终结果， $O(q)$ 用于处理 $q$ 次修改（每次 $O(1)$ ）。
空间复杂度： $O(n \cdot m)$ ，用于存储差分矩阵和原始/最终矩阵。