# C++ Solution with O(n^2) time complexity for initialization and O(1) time complexity for Query

• ``````class NumMatrix {
public:
NumMatrix(vector<vector<int>> &matrix) {
if(matrix.size() == 0)
return ;
sum.resize(matrix.size());
for(int i = 0; i < matrix.size(); ++ i){
vector<int> tmpsum(matrix[0].size());
sum[i] = tmpsum;
for(int j = 0; j < matrix[0].size(); ++ j){
if(!i && !j)
sum[i][j] = matrix[0][0];
else if(!i)
sum[i][j] = sum[i][j - 1] + matrix[i][j];
else if(!j)
sum[i][j] = sum[i - 1][j] + matrix[i][j];
else
sum[i][j] = sum[i][j - 1] + sum[i - 1][j] + matrix[i][j] - sum[i - 1][j - 1];
}
}

}

int sumRegion(int row1, int col1, int row2, int col2) {
if(sum.size() == 0)
return 0;
if(!row1 && !col1)
return sum[row2][col2];
else if(!row1)
return sum[row2][col2] - sum[row2][col1 - 1];
else if(!col1)
return sum[row2][col2] - sum[row1 - 1][col2];
else
return sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 - 1][col1 - 1];
}
private:
vector<vector<int>> sum;
};``````

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