分享 | LeetCode 304 - 二维区域和检索（矩阵不可变）详解

2024.11.04

发布于上海市

百度腾讯阿里巴巴字节跳动学习分享

LeetCode 304 - 二维区域和检索（矩阵不可变）

问题描述

给定一个二维矩阵，需要实现一个类支持多次查询子矩阵的元素和。子矩阵由左上角坐标(row1, col1)和右下角坐标(row2, col2)确定。要求实现两个方法：

初始化方法，接收一个二维矩阵
查询方法，接收左上角和右下角坐标，返回该区域的元素和

题目解析

核心考点：二维前缀和
重点：如何高效处理多次查询
考察内容：
- 前缀和的二维扩展应用
- 矩阵处理
- 查询优化
难点：理解二维前缀和的计算方式和查询公式

解决方案

使用二维前缀和预处理矩阵，将查询操作的时间复杂度优化为O(1)。

预处理：计算从(0,0)到任意位置(i,j)的子矩阵和
查询时：使用容斥原理计算指定区域的和

算法步骤

初始化阶段：
- 创建一个(m+1)×(n+1)的前缀和矩阵
- 对每个位置(i,j)，计算从(0,0)到(i,j)的矩阵和
查询阶段：
- 使用前缀和公式计算指定区域的和
- sum(row1,col1,row2,col2) = preSum[row2+1][col2+1] - preSum[row2+1][col1] - preSum[row1][col2+1] + preSum[row1][col1]

关键点说明

前缀和矩阵的大小比原矩阵多一行一列，用于处理边界情况
计算前缀和时注意坐标的偏移
容斥原理在二维前缀和中的应用
查询公式的理解和使用

代码实现

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            return
            
        rows, cols = len(matrix), len(matrix[0])
        # 创建前缀和矩阵，比原矩阵多一行一列
        self.preSum = [[0] * (cols + 1) for _ in range(rows + 1)]
        
        # 计算二维前缀和
        for i in range(rows):
            for j in range(cols):
                # 当前格子(i,j)的前缀和 = 上方的前缀和 + 左方的前缀和 - 左上角的前缀和 + 当前值
                self.preSum[i + 1][j + 1] = (self.preSum[i + 1][j] + 
                                           self.preSum[i][j + 1] - 
                                           self.preSum[i][j] + 
                                           matrix[i][j])
    
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # 使用容斥原理计算区域和
        return (self.preSum[row2 + 1][col2 + 1] - 
                self.preSum[row2 + 1][col1] - 
                self.preSum[row1][col2 + 1] + 
                self.preSum[row1][col1])

图文解释

考虑一个示例矩阵：

预处理阶段：

前缀和矩阵（第一行和第一列补0）：
0   0   0   0   0
0   3   3   4   8
0   8   14  18  24
0   9   17  21  28
0   13  22  26  34

查询过程说明：
要查询区域(1,1)到(2,2)的和：

使用前缀和矩阵中的值：
- 右下角完整区域: preSum[3][3] = 21
- 减去上方区域: preSum[1][3] = 4
- 减去左方区域: preSum[3][1] = 9
- 加回重复减去的左上角: preSum[1][1] = 3
最终结果: 21 - 4 - 9 + 3 = 11

算法分析

时间复杂度：
- 初始化：O(m*n)，其中m和n是矩阵的行数和列数
- 查询：O(1)
空间复杂度：O(m*n)，需要存储前缀和矩阵

结论

这是一道典型的二维前缀和应用题：
- 通过预处理优化查询效率
- 空间换时间的经典应用
关键技巧：
- 使用额外的行和列处理边界情况
- 利用容斥原理计算区域和
- 正确处理坐标偏移
应用场景：
- 频繁查询矩阵区域和的场景
- 图像处理中的区域统计
- 数据分析中的区域聚合计算

二维前缀和的计算公式

当前格子(i,j)的前缀和计算公式是：

preSum[i + 1][j + 1] = preSum[i + 1][j] + preSum[i][j + 1] - preSum[i][j] + matrix[i][j]

为什么要用 i+1 和 j+1：
- 我们在创建前缀和数组时多加了一行一列（第0行和第0列都是0）
- 这样当我们计算原矩阵位置(i,j)的前缀和时，在前缀和数组中的位置就是(i+1,j+1)
- 这样设计可以避免处理边界情况，使代码更简洁
公式各部分含义是：
1. preSum[i + 1][j]：表示左侧绿色区域的前缀和（从(0,0)到(i+1,j)的矩形区域和）
2. preSum[i][j + 1]：表示上方蓝色区域的前缀和（从(0,0)到(i,j+1)的矩形区域和）
3. preSum[i][j]：表示重叠的棕色区域的前缀和（从(0,0)到(i,j)的矩形区域和，因为被计算了两次，需要减去一次）
4. matrix[i][j]：表示当前位置紫色格子的值
公式的推导：

当前位置的前缀和 = 上方的矩形区域 + 左方的矩形区域 - 重复计算的左上角区域 + 当前格子的值

举个具体例子，假设原矩阵：

3  0  1  4
5  6  3  2

计算位置(1,1)（值为6）的前缀和：

preSum[2][2] = preSum[2][1] + preSum[1][2] - preSum[1][1] + matrix[1][1]
= 8 + 3 - 3 + 6
= 17

这里：

preSum[2][1] = 8 （左边的列前缀和）
preSum[1][2] = 3 （上面的行前缀和）
preSum[1][1] = 3 （左上角的值，需要减去因为被重复计算了）
matrix[1][1] = 6 （当前位置的值）

为什么要这样计算：
- 这样可以保证我们获得从(0,0)到当前位置的所有元素之和
- 通过加减消除重复计算的部分
- 最后加上当前格子的值得到完整的前缀和
使用这个前缀和的好处：
- 预处理后，可以O(1)时间内求得任意矩形区域的和
- 避免了重复计算
- 特别适合需要多次查询区域和的场景

这个公式虽然看起来复杂，但理解了其中的原理后，就会发现这是一个非常巧妙的设计，能够高效地解决二维区域查询的问题。

前缀和矩阵计算过程

对于原矩阵：

让我们一步步计算前缀和矩阵：

首先创建(m+1)×(n+1)的矩阵，第一行和第一列都是0：

0  0  0  0  0
0  *  *  *  *
0  *  *  *  *
0  *  *  *  *
0  *  *  *  *

然后按照公式计算每个位置的值：
preSum[i+1][j+1] = preSum[i+1][j] + preSum[i][j+1] - preSum[i][j] + matrix[i][j]

让我们逐个计算（标记计算的位置）：

第一行第一个元素(0,0)对应的前缀和：
preSum[1][1] = preSum[1][0] + preSum[0][1] - preSum[0][0] + matrix[0][0]
              = 0 + 0 - 0 + 3 = 3

0  0  0  0  0
0  3  *  *  *
0  *  *  *  *
0  *  *  *  *
0  *  *  *  *

继续第一行：

preSum[1][2] = preSum[1][1] + preSum[0][2] - preSum[0][1] + matrix[0][1]
              = 3 + 0 - 0 + 0 = 3

preSum[1][3] = 3 + 0 - 0 + 1 = 4

preSum[1][4] = 4 + 0 - 0 + 4 = 8

结果：
0  0  0  0  0
0  3  3  4  8
0  *  *  *  *
0  *  *  *  *
0  *  *  *  *

计算第二行：

preSum[2][1] = preSum[2][0] + preSum[1][1] - preSum[1][0] + matrix[1][0]
              = 0 + 3 - 0 + 5 = 8

preSum[2][2] = 8 + 3 - 3 + 6 = 14

preSum[2][3] = 14 + 4 - 3 + 3 = 18

preSum[2][4] = 18 + 8 - 4 + 2 = 24

结果：
0  0  0  0  0
0  3  3  4  8
0  8  14 18 24
0  *  *  *  *
0  *  *  *  *

继续计算第三行：

preSum[3][1] = 0 + 8 - 0 + 1 = 9
preSum[3][2] = 9 + 14 - 8 + 2 = 17
preSum[3][3] = 17 + 18 - 14 + 0 = 21
preSum[3][4] = 21 + 24 - 18 + 1 = 28

结果：
0  0  0  0  0
0  3  3  4  8
0  8  14 18 24
0  9  17 21 28
0  *  *  *  *

最后计算第四行：

preSum[4][1] = 0 + 9 - 0 + 4 = 13
preSum[4][2] = 13 + 17 - 9 + 1 = 22
preSum[4][3] = 22 + 21 - 17 + 0 = 26
preSum[4][4] = 26 + 25 - 21 + 1 = 34

最终的前缀和矩阵：
0  0  0  0  0
0  3  3  4  8
0  8  17 21 27
0  9  17 21 28
0  13 22 26 34

现在让我们验证一下查询区域(1,1)到(2,2)的和：

右下角完整区域: preSum[3][3] = 21
减去上方区域: preSum[1][3] = 4
减去左方区域: preSum[3][1] = 9
加回重复减去的左上角: preSum[1][1] = 3
最终结果: 21 - 4 - 9 + 3 = 11

这个结果正确，因为原矩阵中这个区域的值是：

6  3
2  0

6 + 3 + 2 + 0 = 11

解释容斥原理

好的，让我用正确的2×2区域重新解释容斥原理。

对于原矩阵：

要求位置(1,1)到(2,2)的区域和，即这个2×2区域：

6  3
2  0

使用容斥原理计算的代码：

return (self.preSum[row2 + 1][col2 + 1] - 
        self.preSum[row2 + 1][col1] - 
        self.preSum[row1][col2 + 1] + 
        self.preSum[row1][col1])

具体分析每个部分：

self.preSum[row2 + 1][col2 + 1] = self.preSum[3][3]
- 从(0,0)到(2,2)的大区域和
- 包含：[3,0,1, 5,6,3, 1,2,0] = 21
self.preSum[row2 + 1][col1] = self.preSum[3][1]
- 从(0,0)到(2,1)的左侧条形区域
- 包含：[3, 5, 1] = 9
self.preSum[row1][col2 + 1] = self.preSum[1][3]
- 从(0,0)到(1,2)的上方条形区域
- 包含：[3,0,1] = 4
self.preSum[row1][col1] = self.preSum[1][1]
- 左上角重叠区域
- 包含：[3] = 3

最终计算：

目标区域和 = 21 - 9 - 4 + 3 = 11

验证：实际区域 [6,3,2,0] 的和确实等于 11

这就是容斥原理的应用：

先取大区域的和（包含了目标区域）
减去不需要的左边区域
减去不需要的上边区域
加回重复减去的左上角区域

这样就能得到我们想要的2×2区域的和。这种方法的优势是不管要求的区域有多大，都只需要对四个前缀和进行简单的加减运算就能得到结果。