구간 합 질의가 반복될 때
동네 도서관의 운영 담당자가 되었다고 상상해봅시다. 요일별 방문자 수가 [5, 8, 6, 3, 7, 9, 4]처럼 기록되어 있고, 사서들이 하루에도 수십 번 "2일째부터 5일째까지 몇 명 왔어요?" 같은 질문을 합니다.
질문이 들어올 때마다 처음부터 더하면 한 질의에 O(N), 질의가 Q개면 O(N×Q)로 너무 느려집니다. 누적합(prefix sum) 을 쓰면 전처리 한 번 후 모든 질의를 O(1)에 답할 수 있습니다.
누적합의 핵심 아이디어
누적합 배열 prefix를 다음과 같이 정의합니다.
prefix[i] = visitors[0] + visitors[1] + ... + visitors[i-1]즉 prefix[i]는 "처음부터 i개 원소의 합"입니다. 맨 앞에 prefix[0] = 0(아무것도 더하지 않은 합)을 두는 것이 핵심 트릭입니다. 이렇게 하면 구간 합 공식이 깔끔해집니다.
sum(l, r) = prefix[r + 1] - prefix[l]prefix[0] = 0 덕분에 l = 0인 구간도 예외 없이 같은 공식으로 처리됩니다.
직접 따라가 보기
방문자 [5, 8, 6, 3, 7, 9, 4]의 누적합은 다음과 같습니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| prefix | 0 | 5 | 13 | 19 | 22 | 29 | 38 | 42 |
이제 구간 [2, 5]의 합은 직접 더할 필요 없이:
prefix[6] - prefix[2] = 38 - 13 = 25
검산: 6 + 3 + 7 + 9 = 25 ✓구간 [0, 2]도 prefix[3] - prefix[0] = 19 - 0 = 19로 한 번에 나옵니다.
왜 빼면 될까?
prefix[r+1]은 처음부터 r번째까지의 합이고, prefix[l]은 처음부터 l-1번째까지의 합입니다. 둘을 빼면 앞부분(0 ~ l-1)이 정확히 상쇄되고, 우리가 원하는 l ~ r 구간만 남습니다. 그림으로 보면 한눈에 이해됩니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 전처리 | O(N) |
| 질의 (1회) | O(1) |
| 전체 (질의 Q개) | O(N + Q) |
| 공간 | O(N) |
질의가 많을수록 누적합의 위력이 커집니다. 질의 한 번만 한다면 굳이 전처리할 필요가 없지만, 같은 배열에 질의가 반복되면 누적합이 압도적으로 유리합니다.
언제 쓰면 좋을까?
- •배열이 고정되어 있고(원소가 바뀌지 않음) 구간 합 질의만 여러 번 들어올 때
- •"l부터 r까지의 합", "부분 합을 반복해서 묻는" 류의 문제
- •원소가 자주 바뀐다면 누적합 대신 세그먼트 트리나 펜윅 트리를 고려하세요.
알고노트에서 직접 확인하세요
누적합 배열이 어떻게 만들어지고, 각 구간 질의가 뺄셈 한 번으로 어떻게 즉시 답이 나오는지 알고노트에서 단계별로 확인할 수 있습니다.