子矩阵元素加 1

标签: 数组 矩阵 前缀和

难度: Medium

给你一个正整数 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 <= 104
  • 0 <= row1i <= row2i < n
  • 0 <= col1i <= col2i < n

Submission

运行时间: 213 ms

内存: 35.7 MB

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        # 二维差分模板
        diff = [[0] * (n + 2) for _ in range(n + 2)]
        for r1, c1, r2, c2 in queries:
            diff[r1 + 1][c1 + 1] += 1
            diff[r1 + 1][c2 + 2] -= 1
            diff[r2 + 2][c1 + 1] -= 1
            diff[r2 + 2][c2 + 2] += 1

        # 用二维前缀和复原（原地修改）
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]
        # 保留中间 n*n 的部分，即为答案
        diff = diff[1:-1]
        for i, row in enumerate(diff):
            diff[i] = row[1:-1]
        return diff

Explain

此题解使用了二维差分数组的方法来高效处理范围加法问题。首先，创建一个 (n+2)x(n+2) 的差分数组 diff，初始化所有值为0。对于每个查询，使用差分数组的性质，通过更新矩阵的四个关键点来表示子矩阵内所有元素增加1的操作。这四个点是：左上角、右上角+1、左下角+1和右下角+1+1。最后，通过计算二维前缀和来还原出最终的矩阵，这样避免了直接对每个子矩阵内的每个元素进行迭代更新，从而提高效率。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

# 定义解决方案类

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        # 初始化一个 (n+2)x(n+2) 的差分数组
        diff = [[0] * (n + 2) for _ in range(n + 2)]
        # 处理每个查询，更新差分数组的四个关键点
        for r1, c1, r2, c2 in queries:
            diff[r1 + 1][c1 + 1] += 1
            diff[r1 + 1][c2 + 2] -= 1
            diff[r2 + 2][c1 + 1] -= 1
            diff[r2 + 2][c2 + 2] += 1

        # 计算二维前缀和还原最终矩阵
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]
        # 裁剪多余的边界，得到最终的 n*n 矩阵
        diff = diff[1:-1]
        for i, row in enumerate(diff):
            diff[i] = row[1:-1]
        return diff

Explore

在使用二维差分数组处理范围增加操作时，选择使用(n+2)x(n+2)的数组大小主要是为了方便处理边界情况。当我们需要在子矩阵的右侧或下方增加边界值时，使用n+2的尺寸可以确保即使是在矩阵的最右侧或最下侧的边界也能正确处理。例如，当操作需要在最右列或最下行添加值时，不会越界。这样就避免了额外的边界检查，简化了代码实现。

在二维差分数组中，通过更新四个关键点来表示子矩阵内所有元素增加1的操作。这四个点分别是左上角、右上角右侧一列、左下角下方一行、以及右下角右侧一列和下方一行。这种更新方式是局部的，只影响子矩阵的边界，因此不会影响到数组的其他部分。每次更新是针对特定区域的，且通过前缀和的计算，这些局部的更新最终会累积到对应的子矩阵内，其他区域不受影响。

这个公式是二维前缀和的核心，用于计算从矩阵起始点到当前点(i, j)包含的所有值的累积和。这里`diff[i][j - 1]`和`diff[i - 1][j]`分别代表左边和上边的累积前缀和，而`diff[i - 1][j - 1]`则被加了两次（一次在左边累积，一次在上面累积），因此需要减去一次以消除重复计数。这样，每个元素的值都是基于其左上角所有元素的累积效果，确保了正确计算每个点的实际值。

在本题的代码实现中，由于使用了(n+2)x(n+2)的差分数组，实际上已经隐式地处理了查询坐标可能超出矩阵初始边界的情况。即使查询的坐标超出了原始矩阵的边界，由于差分数组的额外边界，这些查询不会引起数组越界错误。此外，代码中没有特别处理这种情况，因为假设查询总是有效的，即在矩阵的合理范围内。如果需要明确处理超出边界的查询，可以在代码中添加条件语句来限制或调整超出边界的坐标值。