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

题目链接

【模板】二维差分

题目描述

给定一个 $n$ 行 $m$ 列的初始矩阵，进行 $q$ 次操作。每次操作将指定的子矩阵中每个元素的值加上一个给定的整数 $c$ 。所有操作完成后，输出最终的矩阵。

解题思路

本题要求对矩阵的子区域进行频繁的增减操作，这是二维差分算法的典型应用场景。

如果直接对每次操作都遍历子矩阵进行更新，时间复杂度为 $O(q \cdot n \cdot m)$ ，在数据量较大时会超时。使用二维差分可以将每次子矩阵的更新操作优化到 $O(1)$ 的时间复杂度。

二维差分的核心是构建一个差分矩阵 $d$ 。对原矩阵 $a$ 进行区间 $[x_1, y_1]$ 到 $[x_2, y_2]$ 增加值 $c$ 的操作，等价于在差分矩阵 $d$ 上进行以下四个点的修改：

$d[x_1][y_1]$ 增加 $c$ ：表示从 $(x_1, y_1)$ 开始的所有元素都增加了 $c$ 。
$d[x_1][y_2+1]$ 减少 $c$ ：为了抵消在 $(x_1, y_2+1)$ 及其右侧和下方区域多加的 $c$ ，需要减去 $c$ 。
$d[x_2+1][y_1]$ 减少 $c$ ：为了抵消在 $(x_2+1, y_1)$ 及其右侧和下方区域多加的 $c$ ，需要减去 $c$ 。
$d[x_2+1][y_2+1]$ 增加 $c$ ：由于在 $(x_1, y_2+1)$ 和 $(x_2+1, y_1)$ 两个区域都减去了 $c$ ，导致在它们重叠的 $(x_2+1, y_2+1)$ 及其右下区域被多减了一次 $c$ ，因此需要加回来。

通过这四次操作，我们就将一次范围更新转化为了四次单点更新，时间复杂度为 $O(1)$ 。

具体的解题步骤如下：

构建初始差分矩阵：读入初始矩阵 $a$ ，通过 insert 操作构建初始的差分矩阵 $d$ 。insert(i, j, i, j, a[i][j]) 相当于对差分矩阵进行 $n \cdot m$ 次单点更新操作。
处理操作：对于 $q$ 次操作中的每一次，都按照上述的四点修改法更新差分矩阵 $d$ 。
还原最终矩阵：所有操作处理完毕后，差分矩阵 $d$ 记录了相对于全零矩阵的所有变化。通过对差分矩阵 $d$ 求二维前缀和，就可以还原出最终的矩阵。还原公式为： $a[i][j] = d[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]$ 。

为了方便处理边界，差分矩阵和最终结果矩阵的大小可以设置为 $(n+2) \times (m+2)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

// 差分矩阵，多开两行两列防止越界
vector<vector<long long>> diff;
int n, m;

// 对子矩阵 [x1, y1] 到 [x2, y2] 增加 c
void insert(int x1, int y1, int x2, int y2, long long c) {
    diff[x1][y1] += c;
    diff[x1][y2 + 1] -= c;
    diff[x2 + 1][y1] -= c;
    diff[x2 + 1][y2 + 1] += c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> n >> m >> q;

    diff.assign(n + 2, vector<long long>(m + 2, 0));

    // 读入初始矩阵，并构建差分矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            long long a;
            cin >> a;
            insert(i, j, i, j, a);
        }
    }

    // 处理 q 次操作
    while (q--) {
        int x1, y1, x2, y2;
        long long c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    // 通过对差分矩阵求前缀和，还原最终矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            cout << diff[i][j] << (j == m ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        in.nextToken();
        int q = (int) in.nval;

        long[][] diff = new long[n + 2][m + 2];

        // 读入初始矩阵，并构建差分矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                in.nextToken();
                long a = (long) in.nval;
                insert(diff, i, j, i, j, a);
            }
        }
        
        // 处理 q 次操作
        for (int k = 0; k < q; k++) {
            in.nextToken();
            int x1 = (int) in.nval;
            in.nextToken();
            int y1 = (int) in.nval;
            in.nextToken();
            int x2 = (int) in.nval;
            in.nextToken();
            int y2 = (int) in.nval;
            in.nextToken();
            long c = (long) in.nval;
            insert(diff, x1, y1, x2, y2, c);
        }
        
        StringBuilder sb = new StringBuilder();
        // 通过对差分矩阵求前缀和，还原最终矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                sb.append(diff[i][j]).append(j == m ? "" : " ");
            }
            sb.append("\n");
        }
        
        System.out.print(sb.toString());
    }

    // 辅助函数：对子矩阵 [x1, y1] 到 [x2, y2] 增加 c
    private static void insert(long[][] diff, int x1, int y1, int x2, int y2, long c) {
        diff[x1][y1] += c;
        diff[x1][y2 + 1] -= c;
        diff[x2 + 1][y1] -= c;
        diff[x2 + 1][y2 + 1] += c;
    }
}

import sys

# 快速输入
input = sys.stdin.readline

def solve():
    n, m, q = map(int, input().split())
    
    # 差分矩阵，多开两行两列防止越界
    diff = [[0] * (m + 2) for _ in range(n + 2)]

    # 辅助函数：对子矩阵 [x1, y1] 到 [x2, y2] 增加 c
    def insert(x1, y1, x2, y2, c):
        diff[x1][y1] += c
        diff[x1][y2 + 1] -= c
        diff[x2 + 1][y1] -= c
        diff[x2 + 1][y2 + 1] += c

    # 读入初始矩阵，并构建差分矩阵
    initial_matrix = []
    for _ in range(n):
        initial_matrix.append(list(map(int, input().split())))
    
    for i in range(n):
        for j in range(m):
            insert(i + 1, j + 1, i + 1, j + 1, initial_matrix[i][j])
    
    # 处理 q 次操作
    for _ in range(q):
        x1, y1, x2, y2, c = map(int, input().split())
        insert(x1, y1, x2, y2, c)

    # 通过对差分矩阵求前缀和，还原最终矩阵
    result_matrix = [[0] * (m + 1) for _ in range(n + 1)]
    output = []
    for i in range(1, n + 1):
        row = []
        for j in range(1, m + 1):
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]
            row.append(str(diff[i][j]))
        output.append(" ".join(row))

    print("\n".join(output))

solve()

算法及复杂度

算法：二维差分
时间复杂度：构建初始差分矩阵的时间复杂度为 $O(n \cdot m)$ ，每次操作的时间复杂度为 $O(1)$ ，还原最终矩阵的时间复杂度为 $O(n \cdot m)$ 。因此，总时间复杂度为 $O(n \cdot m + q)$ 。
空间复杂度：需要一个二维数组来存储差分矩阵，因此空间复杂度为 $O(n \cdot m)$ 。