二维区域和检索 – 矩阵不可变 | LeetCode 304
内容提要
LeetCode 304 要求实现 NumMatrix 类，支持多次查询任意子矩阵的元素和。解法是构建二维前缀和数组，记录以原点为左上角的矩形和，查询时利用容斥原理通过四次加减得到结果。初始化时间复杂度 O(mn)，每次查询 O(1)，空间复杂度 O(mn)。
延伸解读
二维前缀和的核心思路
文章将本题与一维前缀和问题类比，核心是维护一个二维 preSum 数组，记录以原点 (0,0) 为左上角的矩形元素和。查询任意子矩阵时，通过绿色矩阵减去蓝色和橙色矩阵，再加回粉色矩阵的容斥方式，用四次加减得到结果。这种预处理换查询效率的思路，是处理多次区域求和请求的典型手段。
复杂度与适用场景
初始化需遍历整个矩阵构建前缀和，时间复杂度 O(mn)；此后每次 sumRegion 查询仅需常数次加减，为 O(1)。空间上需额外创建一个 (m+1)×(n+1) 的二维前缀和数组，复杂度 O(mn)。结合题目中最多调用 10^4 次查询的限制，这种“一次预处理、多次快速查询”的设计能有效避免每次查询都重复遍历子矩阵。
实现时需留意的边界
文章给出的前缀和数组为 m+1 行 n+1 列，比原矩阵多一行一列，这种设计通常用于简化边界处理，避免查询触及第 0 行或第 0 列时出现越界。题目保证 row1≤row2、col1≤col2 且均在矩阵范围内，因此查询参数本身无需额外校验。矩阵元素可为负值，前缀和相减的容斥逻辑依然成立，不会因负数而失效。
Q&A
LeetCode 304 要求实现什么类，它需要支持哪些操作？
需要实现 NumMatrix 类，包含两个方法：构造函数 NumMatrix(int[][] matrix) 用于初始化矩阵；sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1)、右下角 (row2, col2) 的子矩阵元素总和。
解决 LeetCode 304 的核心思路是什么？
核心思路是构建二维前缀和数组 preSum，记录以原点 (0,0) 为左上角的矩形元素和。查询任意子矩阵时，利用容斥原理通过四次加减运算得到结果。
如何利用二维前缀和数组计算任意子矩阵的元素和？
设 preSum[i][j] 表示从 (0,0) 到 (i-1,j-1) 的矩形和。子矩阵 (row1,col1) 到 (row2,col2) 的和为：preSum[row2+1][col2+1] - preSum[row1][col2+1] - preSum[row2+1][col1] + preSum[row1][col1]。
LeetCode 304 的初始化、查询时间和空间复杂度分别是多少？
初始化时间复杂度 O(mn)，每次查询时间复杂度 O(1)，空间复杂度 O(mn)，其中 m 和 n 分别是矩阵的行数和列数。
二维前缀和数组需要创建多大？
需要创建一个 (m+1) 行 (n+1) 列的二维前缀和数组 sums，其中 m 和 n 分别是原矩阵的行数和列数。
LeetCode 304 和 303 题有什么相似之处？
304 题是 303 题（一维数组区域和检索）的二维版本，两者都使用前缀和思想：303 用一维前缀和，304 用二维前缀和，查询时都通过加减运算快速得到区域和。
