1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class NumMatrix {
private:
vector<vector<int>> dp;
public:
NumMatrix(vector<vector<int>>& matrix) {
int R = matrix.size(); if (R == 0) return;
int C = matrix[0].size(); if (C == 0) return;
dp = vector<vector<int>>(R + 1, vector<int>(C + 1, 0));
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
}
int sumRegion(int row1, int col1, int row2, int col2) {
return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
}
};
|