# C++ easy solution, O(mn) to construct, O(1) to query

• I process the matrix into a sumMatrix of the same size, in which sumMatrix[i][j] stands for the region sum from matrix[0][0] to matrix[i][j]. Say if we wanna query the region sum from matrix[m][n] to matrix[s][t], it goes with

``````sumMatrix[s][t] - sumMatrix[m - 1][t] - sumMatrix[s][n - 1] + sumMatrix[m - 1][n - 1]
``````

Special cases may arise when m equals 0 or n equals 0, which can be handled by construct a one size more sumMatrix, i.e.

``````sumMatrix.size()  = matrix.size() + 1, sumMatrix[i].size() = matrix[i].size() + 1
``````

Or we may handle it within the query as I did.

``````class NumMatrix
{
private:
vector<vector<int>> sumMatrix;
public:
NumMatrix(vector<vector<int>> &matrix): sumMatrix(matrix)
{
if(matrix.empty()) return;
for(int i = 0; i < matrix.size(); ++i)
for(int j = 1; j < matrix[0].size(); ++j)
sumMatrix[i][j] += sumMatrix[i][j - 1];
for(int j = 0; j < matrix[0].size(); ++j)
for(int i = 1; i < matrix.size(); ++i)
sumMatrix[i][j] += sumMatrix[i - 1][j];
}

int sumRegion(int row1, int col1, int row2, int col2)
{
if(row1 < 0 || col1 < 0 || row1 >= sumMatrix.size() || col1 >= sumMatrix[0].size())
return 0;
if(row1 == 0 && col1 == 0)
return sumMatrix[row2][col2];
else if(row1 == 0)
return sumMatrix[row2][col2] - sumMatrix[row2][col1 - 1];
else if(col1 == 0)
return sumMatrix[row2][col2] - sumMatrix[row1 - 1][col2];
return sumMatrix[row2][col2] - sumMatrix[row1 - 1][col2] - sumMatrix[row2][col1 - 1] + sumMatrix[row1 - 1][col1 - 1];
}
};

// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);``````

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