[Prefix Sums] 304. Range Sum Query 2D - Immutable (적분영상)

304. Range Sum Query 2D - Immutable

 

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix
        rows, cols = len(matrix), len(matrix[0])

        # prefixSums[i][j]는 (0,0)부터 (i,j)까지의 누적합을 저장
        self.prefixSums = [[0] * cols for _ in range(rows)]

        for r in range(rows):
            for c in range(cols):
                top = self.prefixSums[r-1][c] if r > 0 else 0          # 위쪽 값
                left = self.prefixSums[r][c-1] if c > 0 else 0         # 왼쪽 값
                topleft = self.prefixSums[r-1][c-1] if r > 0 and c > 0 else 0  # 왼쪽 위 값

                # topleft는 top에도 포함되고, left에도 포함되므로 2번 더해짐 → 한 번 빼줌
                self.prefixSums[r][c] = matrix[r][c] + top + left - topleft

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # (0,0)부터 (row2, col2)까지의 전체 합
        total = self.prefixSums[row2][col2]

        # 위쪽 영역 제외
        up = self.prefixSums[row1-1][col2] if row1 > 0 else 0

        # 왼쪽 영역 제외
        left = self.prefixSums[row2][col1-1] if col1 > 0 else 0

        # 위쪽과 왼쪽 둘 다에서 중복으로 빠진 부분 다시 더해줌
        corner = self.prefixSums[row1-1][col1-1] if row1 > 0 and col1 > 0 else 0

        # 원하는 사각형 영역의 합 = 전체 - 위쪽 - 왼쪽 + 교차영역
        return total - up - left + corner