leetcode

0 class NumMatrix {

1 int n, m;

2 vector<vector<int>> dp;

3

4 public:

5 NumMatrix(vector<vector<int>> &matrix)

6 : n(matrix.size()), m(matrix[0].size()), dp(vector<vector<int>>(n, vector<int>(m, 0))) {

7 for (int i = 0, sum = 0; i < n; i++)

8 sum = dp[i][0] = matrix[i][0] + sum;

9 for (int i = 0, sum = 0; i < m; i++)

10 sum = dp[0][i] = matrix[0][i] + sum;

11 for (int i = 1; i < n; i++) {

12 for (int j = 1; j < m; j++) {

13 dp[i][j] = matrix[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];

14 }

15 }

16 }

17

18 int sumRegion(int x1, int y1, int x2, int y2) {

19 int res = dp[x2][y2];

20 if (x1 > 0) res -= dp[x1 - 1][y2];

21 if (y1 > 0) res -= dp[x2][y1 - 1];

22 if (x1 > 0 && y1 > 0) res += dp[x1 - 1][y1 - 1];

23 return res;

24 }

25 };