题意整理。

给定一个n行m列的矩阵，对这个矩阵进行q次操作，每次操作给定5个参数x1, y1, x2, y2, k，每次操作把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k。
求q次操作之后的矩阵。

方法一（差分数组）

1.解题思路

思路和一维差分的情况非常相似，只是由于矩阵计算会有重叠情况，需要做对应的处理。

首先定义一个差分矩阵，在每次操作中，标记对应增量的边界。
在操作完成之后，遍历差分数组，作前缀和处理，即可还原出每一个位置处的增量。
最后将每一个数加上对应增量，输出操作之后的数组。

图解展示： alt

解释：图中颜色的重叠部分无法表示，每种颜色的区域都是以左上角为起始点全部覆盖的。查询子矩阵的部分等于绿色部分减去橙色部分，再加上多减的红色部分。所以差分标记的时候，绿色部分加k，橙色部分减k，红色部分加k。

2.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        //存放数组元素
        int[][] arr=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i][j]=sc.nextInt();
            }
        }
        //存放增量
        long[][] delta=new long[n+2][m+2];
        //q次操作
        while(q-->0){
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            int k=sc.nextInt();
            //进行差分处理
            delta[x1][y1]+=k;
            delta[x1][y2+1]-=k;
            delta[x2+1][y1]-=k;
            delta[x2+1][y2+1]+=k;
        }
        
        //计算前缀和还原对应元素的增量
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                delta[i+1][j+1]+=delta[i][j+1];
            }
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                delta[i+1][j+1]+=delta[i+1][j];
                System.out.print(delta[i+1][j+1]+arr[i][j]+" ");
            }
            System.out.println();
        }
            
        
    }
}

3.复杂度分析

时间复杂度：如果不作差分处理，每次操作需要 $(x 2 - x 1 + 1) * (y 2 - y 1 + 1)$ 次循环运算，时间复杂度为 $O (x 2 - x 1) * (y 2 - y 1)$ ，使用差分数组之后，只需常数次操作，时间复杂度为 $O (1)$ 。
空间复杂度：需要额外大小为 $(n + 2) * (m + 2)$ 的差分数组，所以空间复杂度为 $O (n * m)$ 。

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

题意整理。

方法一（差分数组）

1.解题思路

2.代码实现

3.复杂度分析