# LeetCode 304. Range Sum Query 2D – Immutable

Problem

To extend the 1D range query problemĀ to 2D, we can still use the same cache approach but with a new “2D” formula.

The new formula for calculating area E will become

E = A – B – C + D

Being translated to the matrix language, it will be:

sum[ (row2,col2) – (row1,col1)] = sum[row2, col2] – sum[row2, col1-1] – sum[row1-1, col2] + sum[row1-1, col1-1]

Where sum[i,j] is the summation of numbers in the rectangle between (0, 0) and (i, j).

My code:

```public class NumMatrix {
int[,] sums;

public NumMatrix(int[,] matrix) {
int height = matrix.GetLength(0);
int width = matrix.GetLength(1);
sums = new int[height, width];
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
if(i == 0 && j == 0) { sums[i,j] = matrix[i,j]; }
else if (i == 0 && j > 0) { sums[i,j] = matrix[i,j] + sums[i,j-1]; }
else if (i > 0 && j == 0) { sums[i,j] = matrix[i,j] + sums[i-1,j]; }
else { sums[i,j] = matrix[i,j] + sums[i-1,j] + sums[i,j-1] - sums[i-1,j-1]; }
}
}
}

public int SumRegion(int row1, int col1, int row2, int col2) {
if(row1 == 0 && col1 == 0) { return sums[row2, col2]; }
else if (row1 == 0 && col1 > 0) { return sums[row2,col2] - sums[row2, col1-1]; }
else if (row1 > 0 && col1 == 0) { return sums[row2,col2] - sums[row1-1, col2]; }
else { return sums[row2, col2] - sums[row2, col1-1] - sums[row1-1, col2] + sums[row1-1, col1-1]; }
}
}

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

Note that I need to specially handle the edge case (row or column equal to zero) in my code.