# LeetCode-Range Sum Query 2D

Datetime:2016-08-23 01:20:24         Topic: LeetCode          Share        Original >>

Given a 2D matrix matrix , find the sum of the elements inside the rectangle defined by its upper left corner ( row 1, col 1) and lower right corner ( row 2, col 2).

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 ≤ row 2 and col 1 ≤ col 2.

Solution:

``` 1 public class NumMatrix {
2     int[][] sums;
3     int rows, cols;
4
5     public NumMatrix(int[][] matrix) {
6         if (matrix.length==0 || matrix[0].length==0) return;
7
8         rows = matrix.length;
9         cols = matrix[0].length;
10         sums = new int[rows][cols];
11
12         for (int i=0;i<rows;i++){
13             int sum = 0;
14             for (int j=0;j<cols;j++){
15                 int sumLastRow = (i==0) ? 0 : sums[i-1][j];
16                 sum += matrix[i][j];
17                 sums[i][j] = sum + sumLastRow;
18             }
19         }
20
21     }
22
23     public int sumRegion(int row1, int col1, int row2, int col2) {
24         if (rows==0 || cols==0) return 0;
25
26         return getSum(row2,col2) - getSum(row2,col1-1) - getSum(row1-1,col2) + getSum(row1-1,col1-1);
27     }
28
29     public int getSum(int row1, int col1){
30         if (row1<0 || col1<0 || row1>=rows || col1>=cols) return 0;
31
32         return sums[row1][col1];
33     }
34 }
35
36
37 // Your NumMatrix object will be instantiated and called as such:
38 // NumMatrix numMatrix = new NumMatrix(matrix);
39 // numMatrix.sumRegion(0, 1, 2, 3);
40 // numMatrix.sumRegion(1, 2, 3, 4);
```