题目描述

题目：给定一个二维数组,在给两个坐标让这两个坐标围成的区域加上某个数字,然后输出此矩阵.

输入样例

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例

2 3 4 1
4 3 4 1
2 2 2 2

算法1

(差分矩阵) $O(n)$

思想：就是通过构造差分数组,然后对差分数组的某些值进行加减,类似于差分一维.主要就是怎么构造二维差分,还有就是让哪些值,哪些值减.最后再把差分数组加起来(方法类似于二维前缀和).

加减公式:

b[x1][y1] += c; 
b[x2+1][y2+1]+=c; 
b[x2+1][y1]-=c;
b[x1][y2+1]-=c

请看图：

时间复杂度：$O(n)$

参考文献：y总

Java 代码

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
    public static final int N = 1010;
    public static int n, m, q;
    public static int[][] a = new int[N][N];
    public static int[][] b = new int[N][N];

    public static void insert(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;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str_01 = reader.readLine().split(" ");
        n = Integer.parseInt(str_01[0]); m = Integer.parseInt(str_01[1]); q = Integer.parseInt(str_01[2]);

        // 接受a数组
        for (int i = 1; i <= n; i++){
            String[] str_02 = reader.readLine().split(" ");
            for (int j = 1; j <= m; j++){
                a[i][j] = Integer.parseInt(str_02[j - 1]);
            }
        }

        // 构造差分数组
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                insert(i, j, i, j, a[i][j]);
            }
        }

        // 加减操作
        for (int i = 1; i <= q; i++){
            String[] str_03 = reader.readLine().split(" ");
            int x1 = Integer.parseInt(str_03[0]); int y1 = Integer.parseInt(str_03[1]);
            int x2 = Integer.parseInt(str_03[2]); int y2 = Integer.parseInt(str_03[3]);
            int c = Integer.parseInt(str_03[4]);
            insert(x1, y1, x2, y2, c);
        }

        // b求前缀和
        // 输出b
        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][j] - b[i - 1][j - 1];
                writer.write(b[i][j] + " ");
            }
            writer.write("\n");
        }
        // 关闭资源
        writer.flush();
        writer.close();
        reader.close();
    }
}