题解 | 【模板】二维差分

这是一道二维差分题，经典表现就是题目要求对一个二维矩阵的子矩阵进行多次累加操作，数组大小设置为d[n+2][m+2]，加2是方便后面操作，防止数组越界

我们先定义一个差分数组，然后定义差分数组的插入函数，当要修改里面的值时，比如赋初值、后面的加k都会通过这个函数来操作

当对x1,y1 至x2,y2这个子矩阵中加k时，我们只需要按照我下面写的操作去操作，可以这样理解，当d[i][j]加k以后要去掉不该加的部分，这个部分包括右边和下面，但是减去两个值后，会导致多减了一份右下角，需要额外加上

当输入初值时，我们就把它传进插入函数，此时的左上角坐标和右下角坐标都为i,j

最后我们需要还原到原数组，这里就不得不提一下，差分数组的前缀和数组是原数组，前缀和数组的差分数组是原数组，要搞清楚这三个数组之间的关系，好进行相应的转换

这里我们可以直接在差分数组上操作，不需要额外创建一个数组

最后打印出来即可

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int m=scanner.nextInt();
		int q=scanner.nextInt();
		long d[][]=new long[n+2][m+2];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				int x=scanner.nextInt();
				insert(d, i, j, i, j, x);
				
			}
		}
		while(q-->0) {
			int x1=scanner.nextInt();
			int y1=scanner.nextInt();
			int x2=scanner.nextInt();
			int y2=scanner.nextInt();
			int k=scanner.nextInt();
			insert(d, x1, y1, x2, y2, k);
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+d[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				System.out.print(d[i][j]+" ");
			}
			System.out.println();
		}


	}
	public static void insert(long d[][],int x1,int y1,int x2,int y2,int k) {
		d[x1][y1]+=k;
		d[x2+1][y1]-=k;
		d[x1][y2+1]-=k;
		d[x2+1][y2+1]+=k;
		
	}
	

}