누적합(prefix sum)은 같은 배열에서 구간 합을 여러 번 물을 때 먼저 떠올릴 수 있는 전처리 방법입니다. 매번 left부터 right까지 다시 더하면 간단하지만, 질문이 많아지는 순간 시간 초과가 나기 쉽습니다.
핵심은 미리 앞부분 합을 저장해 두고, 두 누적값의 차이로 구간 합을 구하는 것입니다. 한 번 준비하면 각 구간 합을 빠르게 계산할 수 있습니다.
누적합을 떠올리는 문제 신호
문제에서 배열이 주어지고, 여러 구간의 합을 반복해서 묻는다면 누적합 후보입니다. 특히 원소 개수 N과 질문 개수 Q가 크면 매번 반복문으로 더하는 방식은 위험합니다.
- 구간 합을 여러 번 구한다
- 배열 값은 중간에 바뀌지 않는다
- left, right 범위가 쿼리로 여러 번 들어온다
- 완전탐색으로는 O(NQ)가 되어 시간 제한에 걸린다
prefix sum 배열을 어떻게 정의할까
가장 실수 적은 방식은 prefix[0] = 0으로 두고, prefix[i]를 앞에서 i개 원소의 합으로 정의하는 것입니다. 그러면 원본 배열의 0번부터 i-1번까지가 prefix[i]에 들어갑니다.
arr = [3, 1, 4, 1, 5]
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]구간 합 공식
prefix[i]가 앞에서 i개 합이라면 arr[left]부터 arr[right]까지의 합은 prefix[right + 1] – prefix[left]입니다. 오른쪽 끝을 포함하려면 right + 1을 써야 합니다.
def range_sum(prefix: list[int], left: int, right: int) -> int:
return prefix[right + 1] - prefix[left]이 방식은 0-based index와 잘 맞습니다. 1-based 입력이 들어오는 문제라면 입력을 0-based로 바꾸거나, prefix 정의를 1-based로 끝까지 유지해야 합니다.
왜 차이를 빼면 구간 합이 될까
prefix[right + 1]에는 0번부터 right번까지의 합이 들어 있습니다. prefix[left]에는 0번부터 left-1번까지의 합이 들어 있습니다. 큰 앞부분 합에서 필요 없는 앞쪽 합을 빼면 left부터 right까지가 남습니다.
arr = [3, 1, 4, 1, 5]
prefix[5] = 3 + 1 + 4 + 1 + 5
prefix[2] = 3 + 1
arr[2..4] = prefix[5] - prefix[2]
= 4 + 1 + 5off-by-one 실수 줄이는 법
누적합에서 가장 흔한 버그는 인덱스 하나 차이입니다. prefix의 의미를 말로 고정해 두면 실수가 줄어듭니다. prefix[i]는 i번째 원소까지가 아니라, 앞에서 i개 원소의 합입니다.
- prefix[0]은 아무것도 더하지 않은 값이다
- arr[i]를 더한 결과는 prefix[i + 1]에 들어간다
- 구간 [left, right]는 prefix[right + 1] – prefix[left]다
- 입력이 1-based인지 0-based인지 처음에 통일한다
2차원 누적합은 언제 필요할까
표나 격자에서 직사각형 영역의 합을 여러 번 구한다면 2차원 누적합을 씁니다. 원리는 1차원과 같지만, 위쪽과 왼쪽을 더하고 겹친 왼쪽 위 영역을 한 번 빼야 합니다.
ps[y + 1][x + 1] = (
grid[y][x]
+ ps[y][x + 1]
+ ps[y + 1][x]
- ps[y][x]
)직사각형 합을 구할 때도 같은 포함-배제 원리를 씁니다. 이런 식이 갑자기 어렵게 느껴진다면 작은 3×3 격자에 숫자를 직접 써보는 것이 가장 빠릅니다.
누적합이 안 맞는 경우
배열 값이 중간에 자주 바뀐다면 단순 누적합은 매번 다시 만들어야 합니다. 이런 경우에는 펜윅 트리나 세그먼트 트리처럼 업데이트와 질의를 함께 처리하는 자료구조가 필요할 수 있습니다.
- 값 변경이 거의 없다: 누적합이 좋다
- 값 변경과 구간 합 질의가 모두 많다: 펜윅 트리나 세그먼트 트리 후보
- 구간에 값을 더하는 업데이트가 많다: 차분 배열도 함께 검토한다
정리
누적합은 구간 합을 빠르게 구하기 위한 전처리입니다. 같은 배열에서 여러 구간 합을 물으면 먼저 떠올리고, prefix 배열의 의미를 일관되게 잡아 off-by-one 실수를 줄이면 됩니다.
prefix sum의 기본 개념은 prefix sum 정의에서 확인할 수 있습니다. 비슷한 구간 문제 사고법은 투 포인터 알고리즘 글과 함께 보면 좋습니다.
