https://www.acmicpc.net/problem/11660

2차원 누적 합(Prefix Sum)을 활용한 구간 합 계산

1. 문제 개요

N×N 크기의 표에 채워진 숫자들이 있을 때, 좌표 $(x_1, y_1)$부터 $(x_2, y_2)$까지의 합을 빠르게 구하는 문제이다.
예를 들어, 아래와 같은 4×4 표가 있다고 가정했을 때

1   2   3   4
2   3   4   5
3   4   5   6
4   5   6   7

• $(2,2)$부터 $(3,4)$까지의 합: $3+4+5+4+5+6 = 27$
• $(4,4)$부터 $(4,4)$까지의 합: $7$

여기서 포인트는
쿼리의 개수가 많아질 때, 매번 직접 더하면 시간 초과가 발생할 수 있으므로 누적 합(prefix sum)을 이용하여 해결 하자는 것이 포인트이다.

---

2. 2차원 누적 합(Prefix Sum) 배열

2.1 누적 합 배열 정의

누적 합 배열 $\texttt{prefix\_sum}$은

를 저장한다고 가정한다.

예를 들어, 위의 표에 대해 누적 합 배열을 만들면 아래와 같이 구성되는 것.
(편의를 위해 0번째 행과 열은 0으로 초기화)

     0    0    0    0    0
     0    1    3    6   10
     0    3    8   15   24
     0    6   15   27   42
     0   10   24   42   64

2.2 누적 합 배열 계산 공식

누적 합 배열은 다음과 같이 구한다.

• $\texttt{arr}[i-1][j-1]$: 현재 위치의 값
• $\texttt{prefix\_sum}[i-1][j]$: 바로 위 영역의 누적 합
• $\texttt{prefix\_sum}[i][j-1]$: 바로 왼쪽 영역의 누적 합
• $\texttt{prefix\_sum}[i-1][j-1]$: 위쪽과 왼쪽 영역이 중복으로 더해졌으므로 이를 한 번 빼준다.

코드로 표현하면:

# N: 표의 크기, arr: 입력 2차원 배열 (0-indexed)
prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]

# 1부터 N까지 1-indexed로 접근 (0번째 행, 열은 0으로 초기화)
for i in range(1, N + 1):
    for j in range(1, N + 1):
        prefix_sum[i][j] = (arr[i-1][j-1]         # 현재 원소 값
                            + prefix_sum[i][j-1]     # 왼쪽 영역의 누적 합
                            - prefix_sum[i-1][j-1])  # 중복된 부분 제거

---

3. 구간 합 계산

3.1 구간 합 공식

구간 $(x_1, y_1)$부터 $(x_2, y_2)$까지의 합은 누적 합 배열을 사용하여 아래 공식으로 $O(1)$ 시간에 구할 수 있다.

3.2 공식 유도 과정

• 전체 영역: ($\texttt{prefix\_sum}[x_2][y_2]$)는 $(1,1)$부터 $(x_2,y_2)$까지의 합
• 위쪽 영역 제거: ($\texttt{prefix\_sum}[x_1-1][y_2]$)는 구간에 포함되지 않아 빼줘야 하는, $(1,1)$부터 $(x_1-1, y_2)$까지의 합
• 왼쪽 영역 제거: ($\texttt{prefix\_sum}[x_2][y_1-1]$)는 $(1,1)$부터 $(x_2, y_1-1)$까지의 합
• 중복 제거: 위쪽과 왼쪽을 제거하면서 겹치는 $(1,1)$부터 $(x_1-1, y_1-1)$ 영역을 두 번 빼주었으므로, 이를 다시 더해준다.

---

4. 전체 코드 (Python)

import sys

# 입력 받기
N, M = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 누적 합 배열 생성 (크기를 N+1 x N+1로 생성하여 0번째 행/열을 0으로 초기화)
prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]

# 2차원 누적 합 배열 계산
for i in range(1, N + 1):
    for j in range(1, N + 1):
        # prefix_sum[i][j]는 (1,1)부터 (i,j)까지의 합
        prefix_sum[i][j] = (arr[i-1][j-1]        # 현재 위치의 값
                            + prefix_sum[i-1][j]    # 위쪽 영역의 누적 합
                            + prefix_sum[i][j-1]    # 왼쪽 영역의 누적 합
                            - prefix_sum[i-1][j-1]) # 중복 영역 제거

# 질의 처리: 각 쿼리에 대해 구간 합 계산
for _ in range(M):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    # 구간 합 공식 적용
    total = (prefix_sum[x2][y2] 
             - prefix_sum[x1-1][y2] 
             - prefix_sum[x2][y1-1] 
             + prefix_sum[x1-1][y1-1])
    print(total)

---