구간 합 구하기 5

백준 11660번: 구간 합 구하기 5

아이디어

각 행별로 합을 기록한다. 1 2 3 4 -> 1 3 6 10
그리고 각 열별로 합을 기록한다.

이렇게 만들어진 2차원 배열에서 (r, c)에 적힌 숫자는 (1, 1)부터 (r, c)까지 커다란 직사각형에 적힌 모든 숫자의 합이다. 이를 잘 이용하면 원하는 범위 (파란색 직사각형)의 합을 구할 수 있다. (그림 참고)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

arr = [[0] + list(map(int, input().split())) for _ in range(N)]
arr.insert(0, [0] * (N + 1))

for row in range(N + 1):
    for col in range(1, N + 1):
        arr[row][col] += arr[row][col - 1]

for col in range(N + 1):
    for row in range(1, N + 1):
        arr[row][col] += arr[row - 1][col]

for _ in range(M):
    r1, c1, r2, c2 = map(int, input().split())
    ans = arr[r2][c2] - arr[r1 - 1][c2] - arr[r2][c1 - 1] + arr[r1 - 1][c1 - 1]
    print(ans)

여담

input = sys.stdin.readline 이거 없으면 안됨