> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/304-range-sum-query-2d-immutable.md).

# 304     Range Sum Query 2D - Immutable

## 304. [Range Sum Query 2D - Immutable](https://leetcode.com/problems/range-sum-query-2d-immutable/description/)

## 1. Question

Given a 2D matrixmatrix, 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 row 1 ≤ row2 and col1 ≤ col2.

## 2. Implementation

**(1) DP**

```java
class NumMatrix {
    int row;
    int col;
    int[][] sum;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }

        row = matrix.length;
        col = matrix[0].length;
        sum = new int[row + 1][col + 1];

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(mn), 空间复杂度O(mn)