# \[304]\[中等]\[动态规划]\[前缀和] 二维区域和检索 - 矩阵不可变

## 题目描述

[304. 二维区域和检索 - 矩阵不可变](https://leetcode-cn.com/problems/range-sum-query-2d-immutable/)

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

![](/files/-MUseOwAkIF6y8ioYeGG)

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

示例：

```
给定 matrix = [
  [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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
```

提示：

* 你可以假设矩阵不可变。
* 会多次调用 sumRegion 方法。
* 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

## 解题思路

依然沿用前缀和的思路, 只不过由一维扩展到了二维.

使用一个二维数组记录前缀和, 由于是二维数组, 这里的前缀和f(i, j)定义为(0, 0)到(i, j)子矩阵的所有元素之和. 那么在计算前缀和时, 还是需要使用动态规划的方法.

在求f(i, j)之前, 我们已经知道了f(i-1, j-1), f(i-1, j), f(i, j-1)的值, 为了覆盖所有方格, 先求f(i-1, j)和f(i, j-1)之和, 但由于加了两次f(i-1, j-1)部分, 需要减去一次f(i-1, j-1)部分, 最后再加上新的matrix(i, j)的值. 因此状态转移公式如下图中所示.

![](/files/-MUseOwFidsMesbCzCdX)

得到前缀和之后, 就要考虑求解大矩阵中任意位置的子矩阵元素之和的问题. 如下图所示, 求点A到点D确定的子矩形中所有元素之和记为S(A, D), 那么S(A, D)就要从S(O, D)中来. 为了减去红色和粉红色的部分, 就要将S(O, D)减去S(O, E)再减去S(O, F). 由于灰色部分减去了两次, 所以要加上一次S(O, G).

公式如下:

S(A, D) = S(O, G) - S(O, E) - S(O, F) + S(O, G)

![](/files/-MUseOwGOSLdmk1RsCVF)

另外还有一点需要特别注意. 如果点D的坐标有一个维度为0, 问题就由二维问题降为一维问题, 这种边界情况在计算前缀和以及求解任意两点的结果时都需要考虑. 而同一维的情况一样, 在创建前缀和矩阵时, 在左侧和上方的外围都添加上一圈0, 这样就将所有问题都转化为矩阵内部的问题, 也就不用考虑边缘情况了.

对比使用与不使用这个技巧的代码复杂度.

不使用:

```python
class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.matrix_prefix = None
        n, m = None, None
        if matrix:
            n = len(matrix)
            if n:
                m = len(matrix[0])
        if n and m:
            self.matrix_prefix = [[0] * m for _ in range(n)]
            self.matrix_prefix[0][0] = matrix[0][0]
            for i in range(1, n):
                self.matrix_prefix[i][0] = self.matrix_prefix[i - 1][0] + matrix[i][0]
            for j in range(1, m):
                self.matrix_prefix[0][j] = self.matrix_prefix[0][j - 1] + matrix[0][j]
            for i in range(1, n):
                for j in range(1, m):
                    self.matrix_prefix[i][j] = self.matrix_prefix[i][j - 1] + \
                                               self.matrix_prefix[i - 1][j] - \
                                               self.matrix_prefix[i - 1][j - 1] + \
                                               matrix[i][j]


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        if self.matrix_prefix is None:
            return 0

        if row1 == 0 and col1 == 0:
            return self.matrix_prefix[row2][col2]

        if row1 == 0:
            return self.matrix_prefix[row2][col2] - self.matrix_prefix[row2][col1 - 1]

        if col1 == 0:
            return self.matrix_prefix[row2][col2] - self.matrix_prefix[row1 - 1][col2]

        return self.matrix_prefix[row2][col2] - \
               self.matrix_prefix[row1 - 1][col2] - \
               self.matrix_prefix[row2][col1 - 1] + \
               self.matrix_prefix[row1 - 1][col1 - 1]
```

使用:

```python
class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            M, N = 0, 0
        else:
            M, N = len(matrix), len(matrix[0])
        self.preSum = [[0] * (N + 1) for _ in range(M + 1)]
        for i in range(M):
            for j in range(N):
                self.preSum[i + 1][j + 1] = self.preSum[i][j + 1] + self.preSum[i + 1][j]  - self.preSum[i][j] + matrix[i][j]

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

## 相关题目

* [\[303\]\[简单\]\[动态规划\]\[前缀和\] 区域和检索 - 数组不可变](/garnet/suan-fa/dong-tai-gui-hua/303-qu-yu-he-jian-suo-shu-zu-bu-ke-bian.md)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/304-er-wei-qu-yu-he-jian-suo-shu-zu-bu-ke-bian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.