Solution
The idea is to store the sum of an element matrix[i][j] with respect to the origin (element matrix[0][0]). That is, element sum[i][j] will store sum of elements from top left corner {0,0} to bottom right corner {i,j}. Below is the idea to calculate the sum (graphs by haoel).
+-----+-+-------+ +--------+-----+ +-----+---------+ +-----+--------+
| | | | | | | | | | | | |
| | | | | | | | | | | | |
+-----+-+ | +--------+ | | | | +-----+ |
| | | | = | | + | | | - | |
+-----+-+ | | | +-----+ | | |
| | | | | | | |
| | | | | | | |
+---------------+ +--------------+ +---------------+ +--------------+
sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + matrix[i-1][j-1]
Once we have the sum array, to calculate the sum of a given rectangle, we use the following idea:
+---------------+ +--------------+ +---------------+ +--------------+ +--------------+
| | | | | | | | | | | | | |
| (r1,c1) | | | | | | | | | | | | |
| +------+ | | | | | | | +---------+ | +---+ |
| | | | = | | | - | | | - | (r1,c2) | + | (r1,c1) |
| | | | | | | | | | | | | |
| +------+ | +---------+ | +---+ | | | | |
| (r2,c2)| | (r2,c2)| | (r2,c1) | | | | |
+---------------+ +--------------+ +---------------+ +--------------+ +--------------+
Below is the implementation.
class NumMatrix {
private:
vector<vector<int>> sum;
public:
NumMatrix(vector<vector<int>>& matrix) {
sum = vector<vector<int>>(matrix.size()+1, vector<int>(matrix[0].size()+1, 0));
for (int i=1; i<=matrix.size(); i++) {
for (int j=1; j<=matrix[0].size(); j++) {
sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1] + sum[row1][col1];
}
};
Time complexity: O(rc) where r = no. of rows and c = no. of columns