# My C++ solution, O(n^2) setup, O(1) sumRegion.

• /*
Conceptually, this code works like this: If we have an initial 'matrix' like the one below

1 2 1 1

2 0 1 2

1 2 1 1

we calculate the 'presum' matrix below, in which every entry presum(i+1, j+1) is the sum all values in the submatrix matrix(0:i, 0:j)

0 0 0 0 0

0 1 3 4 5

0 3 5 7 10

0 4 8 11 15

Then we use sumRegion to add and subtract off blocks until we have the submatrix that we want.
*/

``````class NumMatrix {
private:
/*************************************************************/
vector<vector<int> > presum;

public:
/*************************************************************/
NumMatrix(vector<vector<int> > &matrix) {
if (matrix.size() == 0) return;

presum = vector<vector<int> > (matrix.size()+1, vector<int>(matrix[0].size()+1,0));  //initialize as all zeros

//build presum matrix
for (int i = 1; i < matrix.size()+1; i++){
for (int j =1; j < matrix[0].size()+1; j++){
presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+matrix[i-1][j-1];
}
}
}

/*************************************************************/
int sumRegion(int row1, int col1, int row2, int col2) {
if (presum.size() == 0) return 0;
int sum=0;
sum=presum[row2+1][col2+1]-presum[row1][col2+1]-presum[row2+1][col1]+presum[row1][col1];
return sum;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.