You can extend the previous problem
3070. Count Submatrices with Top-Left Element and Sum Less Than k
and use the same concept to arrive at
class NumMatrix {
public:
vector<vector<int>>dp;
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
dp = vector<vector<int>>(n, vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i==0 && j==0) dp[i][j] = matrix[i][j];
else if(i==0) dp[i][j] = dp[i][j-1] + matrix[i][j];
else if(j==0) dp[i][j] = dp[i-1][j] + matrix[i][j];
else dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int result = dp[row2][col2];
if(row1>0) result-= dp[row1-1][col2];
if(col1>0) result-=dp[row2][col1-1];
if(row1>0 && col1>0) result += dp[row1-1][col1-1];
return result;
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
or if you do not want to handle the edge cases
class NumMatrix {
public:
vector<vector<int>> sum;
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
sum = vector<vector<int>>(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
int sumRegion(int r1, int c1, int r2, int c2) {
r1++; c1++; r2++; c2++;
return sum[r2][c2] - sum[r1 - 1][c2] - sum[r2][c1 - 1] + sum[r1 - 1][c1 - 1];
}
};