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

◎

本节目标

在构造阶段建立带零边界的二维前缀和，随后用四项容斥查询矩形区域。

这道题承接前缀信息与差分：矩阵不再修改，可以把构造成本换成后续的常数时间查询。

查看原题

题意与约束

构造 NumMatrix(matrix) 后，多次查询闭矩形 (row1, col1) 到 (row2, col2) 的元素和。

朴素思路及瓶颈

每次查询都遍历目标矩形并累加元素，单次最坏需要 O(rows * cols) 时间。连续查询的矩形往往大量重叠，同一单元格会被反复读取和相加；由于矩阵构造后不再修改，可以预先汇总二维前缀信息，把这部分重复工作移到一次构造中。

二维容斥

prefix[r][c] 保存原矩阵左上角到 (r - 1, c - 1) 的和，因此额外多一行、一列零。构造时加上上方和左方，减去重复的左上角；查询时同样用四项容斥：整体减去上方和左方，再补回左上角。

代码实现

两份源码的构造器建立 (rows + 1) * (cols + 1) 前缀表，sumRegion 只读取四个位置。C++ 的前缀表使用 long long 保存中间累计量，避免构造过程中发生 32 位整数溢出。

C++

C++17

#include <vector>

using namespace std;

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = rows == 0 ? 0 : matrix[0].size();
        prefix.assign(rows + 1, vector<long long>(cols + 1, 0));
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                prefix[row + 1][col + 1] = matrix[row][col] + prefix[row][col + 1]
                    + prefix[row + 1][col] - prefix[row][col];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        long long sum = prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1]
            - prefix[row2 + 1][col1] + prefix[row1][col1];
        return static_cast<int>(sum);
    }

private:
    vector<vector<long long>> prefix;
};

Python

Python 3

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        rows = len(matrix)
        cols = len(matrix[0]) if rows else 0
        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
        for row in range(rows):
            for col in range(cols):
                self.prefix[row + 1][col + 1] = (
                    matrix[row][col]
                    + self.prefix[row][col + 1]
                    + self.prefix[row + 1][col]
                    - self.prefix[row][col]
                )

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (
            self.prefix[row2 + 1][col2 + 1]
            - self.prefix[row1][col2 + 1]
            - self.prefix[row2 + 1][col1]
            + self.prefix[row1][col1]
        )

复杂度分析

构造时间和空间复杂度均为 O(rows * cols)；每次查询时间复杂度为 O(1)。

易错点

• 不补零边界，令首行首列需要大量特判。
• 容斥时忘记补回被重复减去的左上角。
• 前缀表仍使用 32 位整数，矩阵较大时中间累计量溢出。

模式迁移

静态二维区域查询都可先尝试二维前缀；若矩阵允许频繁更新，则前缀表不能增量维护，应转向二维树状数组或线段树。