筆記：【演算法新手村】[初階]筆記05 - 前綴和(二維)

題目翻譯

給定一個二維矩陣 matrix，請處理多個以下類型的查詢：計算由左上角 (row1, col1) 與右下角 (row2, col2) 所定義的矩形區域內所有元素的總和。
實作 NumMatrix 類別：
NumMatrix(int[][] matrix)：使用二維矩陣 matrix 初始化物件。
int sumRegion(int row1, int col1, int row2, int col2)：回傳矩形區域內的元素總和。
你必須設計一個演算法，使得 sumRegion 的時間複雜度為 O(1)。

解題思路

整理上非常簡單，有甚麼問題可以直接去看【演算法新手村】[初階]筆記05 - 前綴和(二維)，這邊需要注意的是你對sum所引的定義(會影響到你最後求答案時候的索引偏移以及是否需要對索引0檢查越界，可以看LeetCode 303. Range Sum Query - Immutable 詳解，裡面有提到)，還有雖然我用的是long long類型，但是其實int類型也沒有問題。

程式碼實作 (C++)

class NumMatrix {
public:
    vector<vector<long long>> sum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        sum.assign(m+1,vector<long long>(n+1,0));

        for(int i= 1 ; i <= m ; i++){
            for(int j = 1 ; j <= n ; j++){
                sum[i][j] = (long long)sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] 
                + matrix[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1] + sum[row1][col1];
    }
};

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