# Leetcode 304. Range Sum Query 2D - Immutable
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/range-sum-query-2d-immutable/ 。

想法 :

跟1314題一樣先找前綴和，透過前綴和快速求得目標區域的總和。

area[i][j] = area[i-1][j] + area[i][j-1] - area[i-1][j-1];

時間複雜度 : O(r*c)。

程式碼 :

class NumMatrix {
public:
    
    vector<vector<int>> ans;
    NumMatrix(vector<vector<int>>& matrix) {
        ans=matrix;
        
        int r=matrix.size(), c=matrix[0].size();
        
        for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                if(i > 0) ans[i][j]+=ans[i-1][j];
                if(j > 0) ans[i][j]+=ans[i][j-1];
                if(i > 0 && j > 0) ans[i][j]-=ans[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        
        if(row1 > 0 && col1 > 0){
            return  ans[row1-1][col1-1] - ans[row1-1][col2] - ans[row2][col1-1] + ans[row2][col2];
        }
        else if(row1 > 0){
            return ans[row2][col2] - ans[row1-1][col2];
        }
        else if(col1 > 0){
            return ans[row2][col2] - ans[row2][col1-1];
        }
        else{
            return ans[row2][col2];
        }
    }
};

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