Thursday, July 14, 2016

308. Range Sum Query 2D - Mutable

I followed the same way to solve problem “303. Range Sum Query - Immutable”, i.e. dp[i][j] is the sum of rectangle (0, 0, i, j). So the area of rectangle (i1, j1, i2, j2) will be dp[i2][j2]-dp[i1-1][j2]-dp[i2][j1-1]+dp[i1-1][j1-1]. When I revisited this problem, I made mistake in line 16 in red.

1:  class NumMatrix {  
2:  private:  
3:    vector<vector<int>> dp;  
4:    vector<vector<int>> table;  
5:    int rows;  
6:    int cols;  
7:  public:  
8:    NumMatrix(vector<vector<int>> &matrix) {  
9:      table = matrix;  
10:      rows = matrix.size();  
11:      if (rows == 0) return;  
12:      cols = matrix[0].size();  
13:      dp = vector<vector<int>>(rows, vector<int>(cols, 0));  
14:      for (int i = 0; i < rows; i++) {  
15:        for (int j = 0; j < cols; j++) {  
16:          dp[i][j] = (j == 0) ? matrix[i][j] : dp[i][j-1] + matrix[i][j];  
17:        }  
18:        for (int j = 0; j < cols; j++) {  
19:          dp[i][j] += (i == 0) ? 0 : dp[i-1][j];  
20:        }  
21:      }  
22:    }  
23:    void update(int row, int col, int val) {  
24:      int diff = val - table[row][col];  
25:      table[row][col] = val;  
26:      for (int i = row; i < rows; i++) {  
27:        for (int j = col; j < cols; j++) {  
28:          dp[i][j] += diff;  
29:        }  
30:      }  
31:    }  
32:    int sumRegion(int row1, int col1, int row2, int col2) {  
33:      if (row1 == 0 && col1 == 0) return dp[row2][col2];  
34:      if (row1 == 0) return dp[row2][col2]-dp[row2][col1-1];  
35:      if (col1 == 0) return dp[row2][col2]-dp[row1-1][col2];  
36:      return dp[row2][col2]-dp[row1-1][col2]-dp[row2][col1-1]+dp[row1-1][col1-1];  
37:    }  
38:  };  
39:  // Your NumMatrix object will be instantiated and called as such:  
40:  // NumMatrix numMatrix(matrix);  
41:  // numMatrix.sumRegion(0, 1, 2, 3);  
42:  // numMatrix.update(1, 1, 10);  
43:  // numMatrix.sumRegion(1, 2, 3, 4);  

No comments:

Post a Comment