题目

给你一个正整数 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 。

提示：

1 <= n <= 500
1 <= queries.length <= 10^4
0 <= row1i <= row2i < n
0 <= col1i <= col2i < n

解题思路

解决这个问题的核心思想是，将“区域更新”操作转换为“单点更新”操作，从而大大降低时间复杂度。

我们来分析一下为什么需要这样做：

1. 暴力解法（为什么不可行）

最直观的思路是完全模拟题目的要求：

创建一个 n x n 的零矩阵 mat。
遍历每一个查询 [r1, c1, r2, c2]。
对于每个查询，再用两层循环遍历 x (从 r1 到 r2) 和 y (从 c1 到 c2)，然后执行 mat[x][y] += 1。

时间复杂度分析：

设查询的数量为 k (即 queries.length)。
矩阵大小为 n x n。
在最坏的情况下，每个查询都可能覆盖一个 $O(n^2)$ 大小的区域（例如，查询 [0, 0, n-1, n-1]）。
因此，总时间复杂度为 $O(k \cdot n^2)$。

根据题目提示，n 最大为 500，k 最大为 $10^4$。

$O(k \cdot n^2) \approx 10^4 \times 500^2 = 10^4 \times 25 \times 10^4 = 25 \times 10^8$。

这个计算量（25亿次操作）远远超过了常规评测机1秒钟 $10^8$ 次操作的限制，所以暴力解法一定会超时（TLE）。

既然我们只在所有操作之后才需要知道矩阵的最终结果，我们就可以使用“差分”技术。

2.1. 回顾一维差分数组

我们先从一维问题开始。如果给你一个数组，要求你对 [start, end] 区间内的所有数加 1，你会怎么做？

差分数组 diff：
对于每个 [start, end] 操作，我们只修改两个点：
1. diff[start] += 1 （表示从 start 开始，之后的所有数都+1）
2. diff[end + 1] -= 1 （表示从 end + 1 开始，抵消掉前面的+1操作）
如何还原？
- 在处理完所有查询后，我们用“前缀和” (Prefix Sum) 来还原原数组 mat。
- mat[0] = diff[0]
- mat[i] = mat[i-1] + diff[i]
效果：我们将 $O(n)$ 的区间更新变成了 $O(1)$ 的单点更新。最后用 $O(n)$ 的时间还原。总复杂度从 $O(k \cdot n)$ 降到了 $O(k + n)$。

2.2. 推广到二维差分

我们可以把一维的思路推广到二维。

我们要对 (r1, c1) 到 (r2, c2) 的矩形区域加 1。

创建差分矩阵：
我们创建一个差分矩阵 diff，大小可以设为 (n+1) x (n+1) 或 (n+2) x (n+2) 来简化边界处理（避免 +1 操作导致数组越界）。我们这里用 (n+1) x (n+1)。
执行“差分”操作：
对于每一个查询 [r1, c1, r2, c2]，我们只在 diff 矩阵上修改 4 个点。这背后的逻辑是“容斥原理”（Inclusion-Exclusion Principle）：
- diff[r1][c1] += 1
  - 含义：使所有 x >= r1 且 y >= c1 的区域（即以 (r1, c1) 为左上角的无限大矩形）都+1。
- diff[r1][c2 + 1] -= 1
  - 含义：这 “多加” 了。我们需要减去 x >= r1 且 y >= c2 + 1 的区域。
- diff[r2 + 1][c1] -= 1
  - 含义：我们还需要减去 x >= r2 + 1 且 y >= c1 的区域。
- diff[r2 + 1][c2 + 1] += 1
  - 含义：在上面两步减法中，x >= r2 + 1 且 y >= c2 + 1 的区域被减了两次。我们需要加回来一次，以保持平衡。
还原最终矩阵（二维前缀和）：
当我们处理完所有 k 个查询后，diff 矩阵就记录了所有的“变化”。现在，我们需要通过“二维前缀和”来还原出最终的 mat 矩阵。
mat[x][y] 的值，应该是 diff 矩阵中所有 diff[i][j] (其中 i <= x 且 j <= y) 的总和。
我们可以通过一个动态规划的公式来高效计算：
mat[i][j] = diff[i][j] + mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1]
不过，一个更简单、更不容易出错的实现方法是分两步：
- 第一步：计算每行的前缀和
```
for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j++) {
        diff[i][j] += diff[i][j-1];
    }
}
```
  （此时，diff[i][j] 存储了第 i 行，从 0 到 j 列的原始 diff 值的总和）
- 第二步：计算每列的前缀和
```
for (int j = 0; j < n; j++) {
    for (int i = 1; i < n; i++) {
        diff[i][j] += diff[i-1][j];
    }
}
```
  （此时，diff[i][j] 就等于 mat[i][j]，即最终答案）
最后，diff 矩阵（的前 n x n 部分）就是我们要求的答案 mat。

解题步骤：

初始化一个 (n+1) x (n+1) 的差分矩阵 diff 为全零。
遍历所有 queries，对于每个 [r1, c1, r2, c2]：
- diff[r1][c1] += 1
- diff[r1][c2 + 1] -= 1
- diff[r2 + 1][c1] -= 1
- diff[r2 + 1][c2 + 1] += 1
遍历 diff 矩阵，计算二维前缀和（先按行求，再按列求）。
返回 diff 矩阵的左上角 n x n 部分（或者在步骤1中就创建一个 n x n 的 mat，在步骤3中把结果存入 mat）。

新时间复杂度：

处理 k 个查询：每个查询 $O(1)$，总共 $O(k)$。
还原矩阵（二维前缀和）：$O(n^2)$。
总时间复杂度：$O(k + n^2)$。

这个复杂度 $10^4 + 500^2 \approx 260,000$，非常快，可以轻松通过。

具体代码

func rangeAddQueries(n int, queries [][]int) [][]int {

    diff := make([][]int, n + 1)

    for row := range diff {
        diff[row] = make([]int, n + 1)
    }

    for _, q := range queries {
        diff[q[0]][q[1]]++
        diff[q[0]][q[3] + 1]--
        diff[q[2] + 1][q[1]]--
        diff[q[2] + 1][q[3] + 1]++
    }

    // sum row
    for row := range diff {
        for i := 1; i <= n; i++ {
            diff[row][i] += diff[row][i - 1]
        }
    }

    // sum col
    for i := 1; i <= n; i++ {
        for j := range diff[i] {
            diff[i][j] += diff[i - 1][j]
        }
    }

    ans := diff[:n]
    for i := range ans {
        ans[i] = diff[i][:n]
    }

    return ans
    
}

beautifulremi / 2536. 子矩阵元素加 1

题目

解题思路

1. 暴力解法（为什么不可行）

2.1. 回顾一维差分数组

2.2. 推广到二维差分

具体代码