[数据结构与算法]798. 差分矩阵 Java题解 （二维差分）

输入样例：

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

解题思路：

先从原数组中求出差分数组，修改时直接处理差分数组，最后将差分数组视为原数组，求出前缀和数组。

再求以AB为对角线的矩形时，当再A点的差分数组上加上c后，则A的右下角部分黄色区域都会加c，需要将右边灰色区域的(x1,y2 + 1)减去c，将下边浅蓝色区域的（x2 + 1, y1)减去c，最后将紫色区域的（x2 + 1, y2 + 1)的多减去的部分再加回来。

Java代码：

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int m = Integer.parseInt(split[1]);
		int q = Integer.parseInt(split[2]);
		
		int [][]a = new int[n + 2][m + 2];//原数组
		int [][]b = new int[n + 2][m + 2];//差分数组
		for(int i = 1; i <= n; i++) {
			split = br.readLine().split(" ");
			for(int j = 1; j <= m; j++) {
				a[i][j] = Integer.parseInt(split[j - 1]);
				b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];//初始化差分数组
			}
		}
		
		for(int i = 0; i < q; i++) {
			split = br.readLine().split(" ");
			int x1 = Integer.parseInt(split[0]);
			int y1 = Integer.parseInt(split[1]);
			int x2 = Integer.parseInt(split[2]);
			int y2 = Integer.parseInt(split[3]);
			int c = Integer.parseInt(split[4]);
			
			b[x1][y1] += c;//差分核心操作
			b[x1][y2 + 1] -= c;//减去右边多余的部分
			b[x2 + 1][y1] -= c;//减去下边多余的部分
			b[x2 + 1][y2 + 1] += c;//将多减去的再加回来
		}
		
		StringBuilder ans = new StringBuilder();
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];//利用差分数组求前缀和数组
				ans.append(a[i][j] + " ");
			}
			ans.append("\n");
		}
		System.out.print(ans);
	}
}