304. Range Sum Query 2D Immutable - cocoder39/coco39_LC GitHub Wiki

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.region = [[0 for _ in range(n)] for _ in range(m)]

        r = 0
        for j in range(n):
            self.region[0][j] = r + matrix[0][j]
            r = self.region[0][j]

        r = 0
        for i in range(m):
            self.region[i][0] = r + matrix[i][0]
            r = self.region[i][0]

        for i in range(1, m):
            for j in range(1, n):
                self.region[i][j] = self.region[i][j-1] + self.region[i-1][j] + matrix[i][j] - self.region[i-1][j-1]

        
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        region1 = self.region[row2][col2]
        region2 = self.region[row1-1][col1-1] if row1 >= 1 and col1 >= 1 else 0
        region3 = self.region[row2][col1-1] if col1 >= 1 else 0
        region4 = self.region[row1-1][col2] if row1 >= 1 else 0

        return region1 - region3 - region4 + region2

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.region = [[0 for _ in range(n+1)] for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                self.region[i][j] = self.region[i][j-1] + self.region[i-1][j] + matrix[i-1][j-1] - self.region[i-1][j-1]

        
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.region[row2+1][col2+1] + self.region[row1][col1] - self.region[row2+1][col1] - self.region[row1][col2+1]

class NumMatrix {
public:
    NumMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size();
        if (m == 0) {
            return;
        }
        int n = matrix[0].size();
        //sums[i][j] is [0][0] to [i - 1][j - 1]
        sums = vector<vector<int>>(m + 1, vector<int>(n + 1)); 
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1]; 
    }
private:
    vector<vector<int>> sums;
};