304. 二维区域和检索 - 矩阵不可变
题目描述
输入一个二维整数矩阵 matrix，之后会有很多次查询。每次查询给出一个子矩形的左上角 (row1, col1) 和右下角 (row2, col2)，下标从 0 开始，要求算出这个子矩形内所有元素之和。
实现 NumMatrix 类。构造函数接收矩阵 matrix 并完成预处理。方法 sumRegion(row1, col1, row2, col2) 返回行号在 row1 到 row2、列号在 col1 到 col2 之间（都含两端）的元素之和。
矩阵初始化后不再改变。希望每次 sumRegion 只花 O(1) 时间。输入由方法名数组和参数数组组成，输出按顺序给出每次调用的返回值，构造调用记为 null。
示例 1
输入：操作 = ["NumMatrix","sumRegion","sumRegion","sumRegion"] 参数 = [[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]] 输出：[null,8,11,12]
解释：第 2~4 行、第 1~3 列的元素和为 8；第 1~2 行、第 1~2 列的和为 11；第 1~2 行、第 2~4 列的和为 12。
数据范围
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-10^5 <= matrix[i][j] <= 10^50 <= row1 <= row2 < m0 <= col1 <= col2 < nsumRegion最多调用10^4次。
解题思路：二维前缀和
构造二维前缀和 s，s[i][j] 是左上角 i 行 j 列子矩阵的和（多一行一列的 0 做边界）。递推：s[i+1][j+1] = 上 + 左 - 左上 + matrix[i][j]。查询用容斥：大矩形减去上方和左方两块，再加回被减了两次的左上角。
为什么正确
s[i][j] = 所有 matrix[r][c]（r < i，c < j）之和。
复杂度分析
构造 O(mn)，每次查询 O(1)；空间 O(mn)。
易错点
容斥时忘记加回左上角 s[row1][col1]，或者下标没有统一 +1，都会得到错误结果。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
self.s = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
self.s[i + 1][j + 1] = self.s[i][j + 1] + self.s[i + 1][j] - self.s[i][j] + matrix[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
s = self.s
return s[row2 + 1][col2 + 1] - s[row1][col2 + 1] - s[row2 + 1][col1] + s[row1][col1]class NumMatrix {
private final int[][] s;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
s = new int[m + 1][n + 1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + matrix[i][j];
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return s[row2 + 1][col2 + 1] - s[row1][col2 + 1] - s[row2 + 1][col1] + s[row1][col1];
}
}class NumMatrix {
vector<vector<int>> s;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
s.assign(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + matrix[i][j];
}
int sumRegion(int row1, int col1, int row2, int col2) {
return s[row2 + 1][col2 + 1] - s[row1][col2 + 1] - s[row2 + 1][col1] + s[row1][col1];
}
};type NumMatrix struct {
s [][]int
}
func Constructor(matrix [][]int) NumMatrix {
m, n := len(matrix), len(matrix[0])
s := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n+1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + matrix[i][j]
}
}
return NumMatrix{s}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
s := this.s
return s[row2+1][col2+1] - s[row1][col2+1] - s[row2+1][col1] + s[row1][col1]
}var NumMatrix = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const s = this.s = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + matrix[i][j];
};
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
const s = this.s;
return s[row2 + 1][col2 + 1] - s[row1][col2 + 1] - s[row2 + 1][col1] + s[row1][col1];
};class NumMatrix {
private s: number[][];
constructor(matrix: number[][]) {
const m = matrix.length, n = matrix[0].length;
const s = this.s = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + matrix[i][j];
}
sumRegion(row1: number, col1: number, row2: number, col2: number): number {
const s = this.s;
return s[row2 + 1][col2 + 1] - s[row1][col2 + 1] - s[row2 + 1][col1] + s[row1][col1];
}
}其他解法
逐行前缀和只在行方向预处理，查询还要按行累加；二维前缀和再在列方向叠加一次，并用容斥原理（加两角、减两角）把查询降到 O(1)。
解法 2：逐行一维前缀和 时间 初始化 O(mn)，查询 O(m)，空间 O(mn)
对每一行单独求一维前缀和 pre[i][j+1] = pre[i][j] + matrix[i][j]。查询时遍历 row1 到 row2 的每一行，累加 pre[i][col2+1] - pre[i][col1]。
只是把第 303 题的方法逐行套用，不用容斥原理，容易写对。每次查询 O(m)，查询很多时不如二维前缀和。
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.pre = []
for row in matrix:
p = [0]
for x in row:
p.append(p[-1] + x)
self.pre.append(p)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return sum(self.pre[i][col2 + 1] - self.pre[i][col1] for i in range(row1, row2 + 1))class NumMatrix {
private final int[][] pre;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
pre = new int[m][n + 1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
pre[i][j + 1] = pre[i][j] + matrix[i][j];
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int i = row1; i <= row2; i++) sum += pre[i][col2 + 1] - pre[i][col1];
return sum;
}
}class NumMatrix {
vector<vector<int>> pre;
public:
NumMatrix(vector<vector<int>>& matrix) {
for (auto& row : matrix) {
vector<int> p(row.size() + 1, 0);
for (int j = 0; j < (int)row.size(); j++) p[j + 1] = p[j] + row[j];
pre.push_back(p);
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int i = row1; i <= row2; i++) sum += pre[i][col2 + 1] - pre[i][col1];
return sum;
}
};type NumMatrix struct {
pre [][]int
}
func Constructor(matrix [][]int) NumMatrix {
pre := make([][]int, len(matrix))
for i, row := range matrix {
pre[i] = make([]int, len(row)+1)
for j, x := range row {
pre[i][j+1] = pre[i][j] + x
}
}
return NumMatrix{pre}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
sum := 0
for i := row1; i <= row2; i++ {
sum += this.pre[i][col2+1] - this.pre[i][col1]
}
return sum
}var NumMatrix = function(matrix) {
this.pre = matrix.map(row => {
const p = [0];
for (const x of row) p.push(p[p.length - 1] + x);
return p;
});
};
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
let sum = 0;
for (let i = row1; i <= row2; i++) sum += this.pre[i][col2 + 1] - this.pre[i][col1];
return sum;
};class NumMatrix {
private pre: number[][];
constructor(matrix: number[][]) {
this.pre = matrix.map(row => {
const p = [0];
for (const x of row) p.push(p[p.length - 1] + x);
return p;
});
}
sumRegion(row1: number, col1: number, row2: number, col2: number): number {
let sum = 0;
for (let i = row1; i <= row2; i++) sum += this.pre[i][col2 + 1] - this.pre[i][col1];
return sum;
}
}