###### tags: `Leetcode` `medium` `design` `prefix sum` `python` `c++`

# 304. Range Sum Query 2D - Immutable

## [題目連結:] https://leetcode.com/problems/range-sum-query-2d-immutable/

## 題目:
Given a 2D matrix ```matrix```, handle multiple queries of the following type:

* Calculate the **sum** of the elements of ```matrix``` inside the rectangle defined by its **upper left corner** ```(row1, col1)``` and **lower right corner** ```(row2, col2)```.

Implement the ```NumMatrix``` class:

* ```NumMatrix(int[][] matrix)``` Initializes the object with the integer matrix matrix.
* ```int sumRegion(int row1, int col1, int row2, int col2)``` Returns the **sum** of the elements of ```matrix``` inside the rectangle defined by its **upper left corner** ```(row1, col1)``` and **lower right corner** ```(row2, col2)```.

You must design an algorithm where sumRegion works on ```O(1)``` time complexity.


## 解題想法:
* 此題為給一矩陣，設計sumRegion函式為，給定範圍，則求出該範圍內的數字和
* 利用prefix sum概念:
* 預先計算從左上到右下的所有和，對於索求範圍，扣掉其他範圍
* 示意圖:
* 初始:
* 將左邊與上邊多一層0
* 計算prefix sum(右邊括號處)
* 該格=左+上-左上+matrix中該格的值
* 若求藍色部分:
* 黑熱部分-黃色部分+重疊
* 即為prefix中:
* 右下(36)扣掉左邊(17)扣掉上面(10)，加回重複的(3) = 12


* 對於最後求解範圍:
* row1,col1,row2,col2之判斷

## Python:

class NumMatrix(object):
    
    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        m=len(matrix)
        n=len(matrix[0])
        #創一個m+1 * n+1的matrix 
        #並將matrix[i][i]存入sum[i+1]sum[j+1] 對齊右下
        #sum[i][j]為從matrix[0][0]累加到matrix[i-1][j-1]
        self.sum=[[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                #左+上-重複的+當前matrix格的值
                self.sum[i][j]=self.sum[i-1][j]+self.sum[i][j-1]-self.sum[i-1][j-1]+matrix[i-1][j-1]

    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        #扣掉左邊 上面 加回重複扣到的左上
        return self.sum[row2+1][col2+1]-self.sum[row2+1][col1]-self.sum[row1][col2+1]+self.sum[row1][col1]


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

result=NumMatrix([[3, 0, 1, 4, 2], 
                  [5, 6, 3, 2, 1], 
                  [1, 2, 0, 1, 5], 
                  [4, 1, 0, 1, 7], 
                  [1, 0, 3, 0, 5]])
ans=result.sumRegion(2, 1, 4, 3)
print(ans)

## C++:

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        //init
        dp= vector<vector<int>>(m+1, vector<int>(n+1, 0));
        for (int i=1; i<m+1; i++){
            for (int j=1; j<n+1; j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2+1][col2+1]-dp[row2+1][col1]-dp[row1][col2+1]+dp[row1][col1];
    }
private:
    vector<vector<int>> dp;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */