java---矩阵/二维差分算法（每日一道算法2022.7.25）_输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y

题目
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c
其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。

输入
三个初始值，分别为矩阵长宽和数据传入次数
3 4 3

矩阵
1 2 2 1
3 2 2 1
1 1 1 1

计算，每次5个数据，分别为(x1,y1)(x2,y2)以及加减的数
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
1
2
3
4
5
6
7
8
9
10
11
12
13

输出
2 3 4 1
4 3 4 1
2 2 2 2
1
2
3
4

public class 二维差分 {
    public static void main(String[] args) {
        //初始化数据和数组
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), times = in.nextInt();
        int[][] a = new int[n+2][m+2], s = new int[n+2][m+2];

        //首先导入原矩阵
        for (int i = 1; i<=n; i++) {
            for (int j = 1; j<=m; j++) {
                a[i][j] = in.nextInt();
            }
        }
        //创建差分矩阵
        for (int i = 1; i<=n; i++) {
            for (int j = 1; j<=m; j++) {
                insert(s, i, j, i, j, a[i][j]);
            }
        }

        //对差分矩阵进行插入，这样会对还原后的矩阵进行范围行的更改
        while (times -- > 0) {
            int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt(), c = in.nextInt();
            insert(s, x1, y1, x2, y2, c);
        }

        //还原矩阵，也就是将差分矩阵进行前缀和运算
        for (int i = 1; i<=n; i++) {
            for (int j = 1; j<=m; j++) {
                s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
            }
        }

        //输入矩阵内容,因为计算差分时，第一位为0，所以输出就不能直接toString啦，老老实实遍历吧
        for (int i = 1; i<=n; i++) {
            for (int j = 1; j<=m; j++) {
                System.out.print(s[i][j]+" ");
            }
            System.out.println();
        }
    }
    
    //差分矩阵插入的核心计算
    public static void insert(int[][] s, int x1, int y1, int x2, int y2, int c) {
        s[x1][y1] += c;
        s[x2+1][y1] -= c;
        s[x1][y2+1] -= c;
        s[x2+1][y2+1] += c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

其实整体思想和一维差分很类似，可以想象为一维是对直线上的值进行改动
二维矩阵是对x和y轴两条线上的数据进行改动

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作记录和交流