# C++ easy to understand implementation - beat 88%

• My solution simply caches the cumulative sum of each row. Whenever there is an update at (i,j), just update ith row's cumulative sum from position j. i.e ( j - col ) computations every update.

Time complexity of getting sum of a region: O(N), N = # of rows
Time complexity of updating an value: O(M), M = # of cols

``````class NumMatrix {
public:
NumMatrix(vector<vector<int>> matrix) {
int width = matrix.size();
if( width == 0 ) return;
int height = matrix[0].size();
mData = matrix;
mRowCumulative = vector<vector<int>>( width, vector<int>(height, 0) );
for( int i = 0; i < width; i++)
{
int sum = mData[i][0];
mRowCumulative[i][0] = sum;
for( int j = 1; j < height; j++)
{
sum += mData[i][j];
mRowCumulative[i][j] = sum;
}
}
}

void update(int row, int col, int val) {
mData[row][col] = val;
for( int j = col; j < mData[row].size(); j++)
{
int prev_sum = j == 0 ? 0 : mRowCumulative[row][j-1];
mRowCumulative[row][j] = prev_sum + mData[row][j];
}
}

int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for( int i = row1; i <= row2; i++)
{
int prev_sum = col1 == 0 ? 0 : mRowCumulative[i][col1-1];
sum += mRowCumulative[i][col2] - prev_sum;
}
return sum;
}
private:
vector<vector<int>> mData;
vector<vector<int>> mRowCumulative;
};

/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* obj.update(row,col,val);
* int param_2 = obj.sumRegion(row1,col1,row2,col2);
*/
``````

• Nice Solution. Not sure why this solution can be so quick.

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