What is the optimal way to handle multiple sum queries on a 2D matrix?

The optimal solution is to use a prefix sum matrix, where each query can be answered in constant time, O(1), by using precomputed sums.

How do you avoid recalculating the sum for every query in Range Sum Query 2D - Immutable?

By storing the sum of submatrices in a prefix sum matrix, each query can be answered in constant time without recalculating sums.

What data structure is best suited for the Range Sum Query 2D - Immutable problem?

The best data structure is a 2D prefix sum matrix that stores cumulative sums and allows fast query processing in O(1) time.

How does the space complexity of the prefix sum matrix affect the solution?

The space complexity of the prefix sum matrix is O(m * n), which is manageable within the problem's constraints and necessary for efficient querying.

Can you modify the Range Sum Query 2D - Immutable to handle dynamic updates?

Yes, by modifying the prefix sum matrix after each update, you can handle dynamic updates, but this will increase the complexity of the solution.

#304

Medium

auto_awesome前缀和

LeetCode 题解工作台

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

给定一个二维矩阵 matrix ，以下类型的多个请求：计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行…

数组设计矩阵前缀和

题目描述

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

示例 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]

解释:
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-10⁵ <= matrix[i][j] <= 10⁵
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 10⁴ 次 sumRegion 方法

lightbulb

解题思路

方法一：二维前缀和

我们用 $s[i + 1][j + 1]$ 表示第 $i$ 行第 $j$ 列左上部分所有元素之和，下标 $i$ 和 $j$ 均从 $0$ 开始。可以得到以下前缀和公式：

s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + nums[i][j]

那么分别以 $(x_1, y_1)$ 和 $(x_2, y_2)$ 为左上角和右下角的矩形的元素之和为：

s[x_2 + 1][y_2 + 1] - s[x_2 + 1][y_1] - s[x_1][y_2 + 1] + s[x_1][y_1]

我们在初始化方法中预处理出前缀和数组 $s$ ，在查询方法中直接返回上述公式的结果即可。

初始化的时间复杂度为 $O(m \times n)$ ，查询的时间复杂度为 $O(1)$ 。空间复杂度为 $O(m \times n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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, row in enumerate(matrix):
            for j, v in enumerate(row):
                self.s[i + 1][j + 1] = (
                    self.s[i][j + 1] + self.s[i + 1][j] - self.s[i][j] + v
                )

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


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should demonstrate an understanding of prefix sums and how to apply them to a 2D matrix.
question_mark
Look for familiarity with space and time trade-offs, especially regarding the need to store and update the prefix sum matrix.
question_mark
Pay attention to how candidates approach the optimization of the query time, ensuring O(1) complexity for sumRegion.

warning

常见陷阱

外企场景

error
Failing to precompute the prefix sum matrix, leading to inefficient solutions.
error
Incorrectly handling the boundaries of the matrix when calculating sumRegion, which can result in out-of-bounds errors.
error
Overcomplicating the solution by not focusing on the O(1) query requirement, instead implementing less efficient methods.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing for dynamic updates to the matrix, which would require modifying the prefix sum after each update.
arrow_right_alt
Handling queries for different types of submatrices, such as those that cover rows or columns.
arrow_right_alt
Improving space efficiency by using rolling sums or other data structures for large matrices.

help

常见问题

外企场景

继续练习

#363 矩形区域不超过 K 的最大数值和 #731 我的日程安排表 II #1074 元素和为目标值的子矩阵数量