LeetCode 304: Range Sum Query 2D - Immutable (2D Prefix Sum Inclusion-Exclusion)
LeetCode 304Prefix SumMatrixToday we solve LeetCode 304 - Range Sum Query 2D - Immutable.
Source: https://leetcode.com/problems/range-sum-query-2d-immutable/
English
Problem Summary
Design a NumMatrix class that supports fast rectangle sum queries on a fixed matrix. The method sumRegion(row1, col1, row2, col2) should return the sum of elements inside the rectangle corners.
Key Idea
Use a 2D prefix sum table pre with one extra row and one extra column. Then each rectangle sum is computed in constant time by inclusion-exclusion.
Algorithm
1) Build pre of size (m+1) x (n+1).
2) Transition: pre[i][j] = matrix[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1].
3) Query rectangle (r1,c1) to (r2,c2) with
pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1].
Complexity
Preprocessing takes O(mn). Each query is O(1). Extra space is O(mn).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class NumMatrix {
private final int[][] pre;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
int n = m == 0 ? 0 : matrix[0].length;
pre = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
pre[i][j] = matrix[i - 1][j - 1]
+ pre[i - 1][j]
+ pre[i][j - 1]
- pre[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int r1 = row1, c1 = col1, r2 = row2 + 1, c2 = col2 + 1;
return pre[r2][c2] - pre[r1][c2] - pre[r2][c1] + pre[r1][c1];
}
}type NumMatrix struct {
pre [][]int
}
func Constructor(matrix [][]int) NumMatrix {
m := len(matrix)
n := 0
if m > 0 {
n = len(matrix[0])
}
pre := make([][]int, m+1)
for i := range pre {
pre[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
pre[i][j] = matrix[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]
}
}
return NumMatrix{pre: pre}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
r1, c1 := row1, col1
r2, c2 := row2+1, col2+1
return this.pre[r2][c2] - this.pre[r1][c2] - this.pre[r2][c1] + this.pre[r1][c1]
}class NumMatrix {
private:
vector<vector<int>> pre;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = m ? matrix[0].size() : 0;
pre.assign(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
pre[i][j] = matrix[i - 1][j - 1]
+ pre[i - 1][j]
+ pre[i][j - 1]
- pre[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int r1 = row1, c1 = col1, r2 = row2 + 1, c2 = col2 + 1;
return pre[r2][c2] - pre[r1][c2] - pre[r2][c1] + pre[r1][c1];
}
};class NumMatrix:
def __init__(self, matrix):
m = len(matrix)
n = len(matrix[0]) if m else 0
self.pre = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
self.pre[i][j] = (
matrix[i - 1][j - 1]
+ self.pre[i - 1][j]
+ self.pre[i][j - 1]
- self.pre[i - 1][j - 1]
)
def sumRegion(self, row1, col1, row2, col2):
r1, c1 = row1, col1
r2, c2 = row2 + 1, col2 + 1
return self.pre[r2][c2] - self.pre[r1][c2] - self.pre[r2][c1] + self.pre[r1][c1]var NumMatrix = function(matrix) {
const m = matrix.length;
const n = m ? matrix[0].length : 0;
this.pre = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
this.pre[i][j] = matrix[i - 1][j - 1]
+ this.pre[i - 1][j]
+ this.pre[i][j - 1]
- this.pre[i - 1][j - 1];
}
}
};
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
const r1 = row1, c1 = col1, r2 = row2 + 1, c2 = col2 + 1;
return this.pre[r2][c2] - this.pre[r1][c2] - this.pre[r2][c1] + this.pre[r1][c1];
};中文
题目概述
实现一个 NumMatrix 类，输入矩阵固定不变，多次查询子矩形区域和。每次调用 sumRegion(row1, col1, row2, col2) 返回对应矩形内元素总和。
核心思路
构建二维前缀和 pre（多开一行一列，方便处理边界）。这样每次查询都能通过容斥在 O(1) 时间得到答案。
算法步骤
1）初始化 pre 大小为 (m+1) x (n+1)。
2）状态转移：pre[i][j] = matrix[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]。
3）查询时使用容斥：
pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]。
复杂度分析
预处理时间 O(mn)，单次查询时间 O(1)，额外空间 O(mn)。
参考实现（Java / Go / C++ / Python / JavaScript）
class NumMatrix {
private final int[][] pre;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
int n = m == 0 ? 0 : matrix[0].length;
pre = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
pre[i][j] = matrix[i - 1][j - 1]
+ pre[i - 1][j]
+ pre[i][j - 1]
- pre[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int r1 = row1, c1 = col1, r2 = row2 + 1, c2 = col2 + 1;
return pre[r2][c2] - pre[r1][c2] - pre[r2][c1] + pre[r1][c1];
}
}type NumMatrix struct {
pre [][]int
}
func Constructor(matrix [][]int) NumMatrix {
m := len(matrix)
n := 0
if m > 0 {
n = len(matrix[0])
}
pre := make([][]int, m+1)
for i := range pre {
pre[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
pre[i][j] = matrix[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]
}
}
return NumMatrix{pre: pre}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
r1, c1 := row1, col1
r2, c2 := row2+1, col2+1
return this.pre[r2][c2] - this.pre[r1][c2] - this.pre[r2][c1] + this.pre[r1][c1]
}class NumMatrix {
private:
vector<vector<int>> pre;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = m ? matrix[0].size() : 0;
pre.assign(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
pre[i][j] = matrix[i - 1][j - 1]
+ pre[i - 1][j]
+ pre[i][j - 1]
- pre[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int r1 = row1, c1 = col1, r2 = row2 + 1, c2 = col2 + 1;
return pre[r2][c2] - pre[r1][c2] - pre[r2][c1] + pre[r1][c1];
}
};class NumMatrix:
def __init__(self, matrix):
m = len(matrix)
n = len(matrix[0]) if m else 0
self.pre = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
self.pre[i][j] = (
matrix[i - 1][j - 1]
+ self.pre[i - 1][j]
+ self.pre[i][j - 1]
- self.pre[i - 1][j - 1]
)
def sumRegion(self, row1, col1, row2, col2):
r1, c1 = row1, col1
r2, c2 = row2 + 1, col2 + 1
return self.pre[r2][c2] - self.pre[r1][c2] - self.pre[r2][c1] + self.pre[r1][c1]var NumMatrix = function(matrix) {
const m = matrix.length;
const n = m ? matrix[0].length : 0;
this.pre = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
this.pre[i][j] = matrix[i - 1][j - 1]
+ this.pre[i - 1][j]
+ this.pre[i][j - 1]
- this.pre[i - 1][j - 1];
}
}
};
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
const r1 = row1, c1 = col1, r2 = row2 + 1, c2 = col2 + 1;
return this.pre[r2][c2] - this.pre[r1][c2] - this.pre[r2][c1] + this.pre[r1][c1];
};
Comments