304. Range Sum Query 2D - Immutable

Suppose we have a matrix dp[i][j] records the sum of rectangle of (0, 0, i, j). Then the sum of rectangle of (row1, col1, row2, col2) can be calculated by four rectangles: (0, 0, row2, col2), (0, 0, row1-1, col2), (0, 0, row2, col1-1), (0, 0, row1-1, col2-1). If you overlap these four rectangles, you'll find that:
(row1, col1, row2, col2) = (0, 0, row2, col2) - (0, 0, row1-1, col2) - (0, 0, row2, col1-1) + (0, 0, row1-1, col2-1)

1:  class NumMatrix {  
2:  private:  
3:    vector<vector<int>> sumMatrix;  
4:  public:  
5:    NumMatrix(vector<vector<int>> &matrix) {  
6:      if (matrix.size() > 0 && matrix[0].size() > 0) {  
7:        int rows = matrix.size();  
8:        int cols = matrix[0].size();  
9:        vector<vector<int>> dp(rows+1, vector<int>(cols+1, 0));  
10:        for (int i = 1; i <= rows; i++) {  
11:          int rowSum = 0;  
12:          for (int j = 1; j <= cols; j++) {  
13:            rowSum += matrix[i-1][j-1];  
14:            dp[i][j] = rowSum + dp[i-1][j];  
15:          }  
16:        }  
17:        sumMatrix = dp;  
18:      }  
19:    }  
20:    int sumRegion(int row1, int col1, int row2, int col2) {  
21:      return sumMatrix[row2+1][col2+1] - sumMatrix[row2+1][col1] - sumMatrix[row1][col2+1] + sumMatrix[row1][col1];  
22:    }  
23:  };  
24:  // Your NumMatrix object will be instantiated and called as such:  
25:  // NumMatrix numMatrix(matrix);  
26:  // numMatrix.sumRegion(0, 1, 2, 3);  
27:  // numMatrix.sumRegion(1, 2, 3, 4);