1. 문제 소개

2536. Increment Submatrices by One

2. 나의 풀이

처음에는 단순하게 더하기만 하면 된다고 생각했는데 이 경우 시간초과가 날 수 있다.
따라서 차분 기록과 누적 합을 사용하기로 했다.
시간복잡도는 $O(q + n^2)$이다.

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        diff = [[0] * (n + 1) for _ in range(n + 1)]           # (n+1)×(n+1) 차분 배열(경계 처리용 패딩)

        for r1, c1, r2, c2 in queries:                         # 각 쿼리에 대해 2D 차분 기록
            diff[r1][c1] += 1                                  # 좌상단 +1
            diff[r2+1][c1] -= 1                                # 하한 경계 아래 -1
            diff[r1][c2+1] -= 1                                # 우측 경계 오른쪽 -1
            diff[r2+1][c2+1] += 1                              # 우하단 바깥 +1 (상쇄용)

        mat = [[0] * n for _ in range(n)]                      # 결과 행렬
        for i in range(n):                                     # 2D 누적합(가우스 사각형 공식)로 복원
            for j in range(n):
                up = mat[i - 1][j] if i > 0 else 0             # 위쪽 누적
                left = mat[i][j - 1] if j > 0 else 0           # 왼쪽 누적
                diag = mat[i - 1][j - 1] if i > 0 and j > 0 else 0  # 겹친 영역 보정
                mat[i][j] = diff[i][j] + up + left - diag      # 포함-배제 원리로 최종값 복원

        return mat                                             # 모든 쿼리 적용 후 최종 행렬 반환

3. 다른 풀이

시간복잡도는 똑같은 $O(q + n^2)$이지만 diff배열을 만들지 않고, 바로 행렬을 만들어 계산을 진행했다.

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        res = [[0] * n for _ in range(n)]              # n×n 결과 행렬(차분 기록용)

        for r1, c1, r2, c2 in queries:                 # 각 쿼리 처리
            r2 += 1; c2 += 1                           # 경계 처리(아래·오른쪽 한 칸 확장)
            res[r1][c1] += 1                           # 좌상단 +1 → 구간 시작점
            if c2 < n:
                res[r1][c2] -= 1                       # 우측 경계 바로 다음 칸 -1
            if r2 < n:
                res[r2][c1] -= 1                       # 하단 경계 바로 아래 칸 -1
                if c2 < n:
                    res[r2][c2] += 1                   # 우하단 모서리 +1 (상쇄)

        # delta[j]는 열 단위 누적 효과(세로 방향)를 추적
        delta = [0] * n
        for i, row in enumerate(res):                  # 행 단위 누적
            acc = 0                                    # 현재 행의 누적합(가로 방향)
            for j, x in enumerate(row):
                delta[j] += x                          # 위쪽에서 내려오는 누적 영향 추가
                acc += delta[j]                        # 왼쪽 누적(가로 방향 포함)
                res[i][j] = acc                        # 최종 누적 결과 저장

        return res                                     # 모든 쿼리 적용 후 최종 행렬 반환

4. 결론

바로바로 계산하는 것이 아니라 한 번에 계산하는 것이 중요 포인트이다.