304. Range Sum Query 2D – Immutable

Description:

https://leetcode.com/problems/continuous-subarray-sum/#/description

Boundary:

Should consider when the dimension of matirix is 0;

Algorithm:

1. Because there are many calls to sumRegion() function, we should pre-store the sums instead of calculating for each time
2. Should have 0 row and 0 column.

Code: 

class NumMatrix {
public:
NumMatrix(vector<vector<int>> matrix) {
m = matrix.size();
n = m > 0 ? matrix[0].size():0;
sums = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

sums[1][1] = matrix[0][0];

for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] – sums[i][j] + matrix[i][j];
}
}

}

int sumRegion(int row1, int col1, int row2, int col2) {
return sums[row2 + 1][col2 + 1] – sums[row1][col2 + 1] – sums[row2 + 1][col1] + sums[row1][col1];
}
private:
int m, n;
vector<vector<int>> sums;
};