> For the complete documentation index, see [llms.txt](https://loghead.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/range-sum-query-2d-immutable.md).

# Range Sum Query 2D - Immutable

> Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
>
> ![Range Sum Query 2D](https://leetcode.com/static/images/courses/range_sum_query_2d.png)\
> The above rectangle (with the red border) is defined by (row1, col1) = **(2, 1)** and (row2, col2) = **(4, 3)**, which contains sum = **8**.
>
> **Example:**
>
> ```
> Given 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
> ```
>
> **Note:**
>
> 1. You may assume that the matrix does not change.
> 2. There are many calls to sumRegion function.
> 3. You may assume that row1 ≤ row2 and col1 ≤ col2.

这题在前一题基础上，扩展成2d的问题。思路还是一样，用类似dp的方法算 prefixsum\[i]\[j]

思路如下，在leetcode discuss抄来的，懒得自己写了。

计算 prefix sum array:

```
+-----+-+-------+     +--------+-----+     +-----+---------+     +-----+--------+     +---------------+ 
|     | |       |     |        |     |     |     |         |     |     |        |     |               |
|     | |       |     |        |     |     |     |         |     |     |        |     |               |
+-----+-+       |     +--------+     |     |     |         |     +-----+        |     |     +-+       | 
|     | |       |  =  |              |  +  |     |         |  -  |              |  +  |     | |       |
+-----+-+       |     |              |     +-----+         |     |              |     |     +-+       |
|               |     |              |     |               |     |              |     |               |
|               |     |              |     |               |     |              |     |               |
+---------------+     +--------------+     +---------------+     +--------------+     +---------------+

   sums[i][j]      =    sums[i-1][j]    +     sums[i][j-1]    -   sums[i-1][j-1]   +      matrix[i-1][j-1]
```

取值：

```
+---------------+   +--------------+   +---------------+   +--------------+   +--------------+
|               |   |         |    |   |   |           |   |         |    |   |   |          |
|   (r1,c1)     |   |         |    |   |   |           |   |         |    |   |   |          |
|   +------+    |   |         |    |   |   |           |   +---------+    |   +---+          |
|   |      |    | = |         |    | - |   |           | - |      (r1,c2) | + |   (r1,c1)    |
|   |      |    |   |         |    |   |   |           |   |              |   |              |
|   +------+    |   +---------+    |   +---+           |   |              |   |              |
|        (r2,c2)|   |       (r2,c2)|   |   (r2,c1)     |   |              |   |              |
+---------------+   +--------------+   +---------------+   +--------------+   +--------------+
```

程序如下

```python
class NumMatrix(object):

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            m = n = 0
        else:
            m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in xrange(m + 1)]
        for i in xrange(1, m + 1):
            for j in xrange(1, n + 1):
                self.prefix[i][j] = self.prefix[i-1][j] + self.prefix[i][j-1] \
                                    - self.prefix[i-1][j-1] + matrix[i-1][j-1]


    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        return self.prefix[row2 + 1][col2 + 1] + self.prefix[row1][col1] \
               - self.prefix[row1][col2 + 1] - self.prefix[row2 + 1][col1]
```