【数据结构-二维差分】力扣2536. 子矩阵元素加 1
给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。
另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：
找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵，将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。
返回执行完所有操作后得到的矩阵 mat 。
示例 1：
输入：n = 3, queries = [[1,1,2,2],[0,0,1,1]]
输出：[[1,1,0],[1,2,1],[0,1,1]]
解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵、执行完第二个操作后的矩阵。
- 第一个操作：将左上角为 (1, 1) 且右下角为 (2, 2) 的子矩阵中的每个元素加 1 。
- 第二个操作：将左上角为 (0, 0) 且右下角为 (1, 1) 的子矩阵中的每个元素加 1 。
示例 2：
输入：n = 2, queries = [[0,0,1,1]]
输出：[[1,1],[1,1]]
解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵。
- 第一个操作：将矩阵中的每个元素加 1 。
二维差分
class Solution {
public:vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {vector<vector<int>> diff(n+2, vector<int>(n+2));for(auto &query : queries){int r1 = query[0], c1 = query[1], r2 = query[2], c2 = query[3];diff[r1+1][c1+1]++;diff[r2+2][c1+1]--;diff[r1+1][c2+2]--;diff[r2+2][c2+2]++;}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];}}diff.erase(diff.begin());diff.erase(diff.end());for(auto& row : diff){row.erase(row.begin());row.erase(row.end());}return diff;}
};
在二维差分中，我们要先求出二维的差分矩阵，然后在将其进行前缀和相加得到我们所想要的矩阵。在构造差分矩阵中，我们构造了一个大小(n+2) * (n+2)的矩阵。
有人会想问，为什么在一维差分中，差分只需要多1的空间，而在二维差分的矩阵中，我们有diff[r2+2][c2+2]++;，实际上是因为，我们在后面需要运用到前缀和来累加差分矩阵，而前缀和需要我们第0行和第0列都为0，用来辅助计算，而差分又使最后一行和最后一列多出来用来辅助差分计算，所以最后就需要多出两行和两列的空间。
计算完差分数组后，就计算差分的前缀和，就构成了我们答案需要的矩阵。但是前缀和运算后，由于矩阵的外面一圈都是用来辅助计算的，所以都要去掉。去掉外面一圈后，剩下的矩阵就是我们所需要的矩阵。