실버 III누적 합이란?
누적 합(prefix sum) 은 배열의 "앞에서부터의 합"을 미리 계산해 두어, 임의
구간의 합을 \(O(1)\)에 구하는 전처리 기법입니다.
구간 합을 매번 반복문으로 더하면 한 번에 \(O(N)\), 질의가 \(Q\)개면 \(O(NQ)\)입니다.
누적 합을 쓰면 전처리 \(O(N)\) 후 각 질의 \(O(1)\), 전체 \(O(N + Q)\)로 줄어듭니다.
1. 핵심 아이디어
prefix[i]를 "처음부터 \(i\)번째까지의 합"으로 정의하면, 구간 \([l, r]\)의 합은
두 누적 합의 차로 구해집니다.
$$ \text{sum}(l, r) = \text{prefix}[r] - \text{prefix}[l-1] $$
a = [3, 1, 4, 1, 5]
prefix = [3, 4, 8, 9, 14] (앞에서부터 누적)
sum(1,3) = prefix[3] - prefix[0] = 9 - 3 = 6 (a[1]+a[2]+a[3] = 1+4+1)
큰 합에서 앞부분을 빼면 가운데 구간만 남는다 — 이 한 줄이 전부입니다.
2. 왜 빠른가
전처리는 배열을 한 번 훑으며 누적하므로 \(O(N)\). 이후 어떤 구간 합이든 뺄셈
한 번, 즉 \(O(1)\)입니다. 질의가 많을수록 이득이 커집니다.
| 방식 | 전처리 | 질의 1회 | 질의 \(Q\)회 |
|---|---|---|---|
| 매번 더하기 | 없음 | \(O(N)\) | \(O(NQ)\) |
| 누적 합 | \(O(N)\) | \(O(1)\) | \(O(N + Q)\) |
3. 1-인덱스가 편하다
누적 합은 \(\text{prefix}[l-1]\)을 자주 쓰기 때문에 \(l = 0\)에서 음수 인덱스가
생깁니다. prefix[0] = 0으로 두고 1-인덱스로 다루면 경계 처리가 깔끔해집니다.
$$ \text{prefix}[i] = \text{prefix}[i-1] + a[i], \quad \text{sum}(l, r) = \text{prefix}[r] - \text{prefix}[l-1] $$
4. 2차원으로 확장
격자에서 직사각형 영역의 합도 같은 원리로 \(O(1)\)에 구합니다. 포함-배제가
핵심입니다.
$$ \text{sum} = P[r_2][c_2] - P[r_1-1][c_2] - P[r_2][c_1-1] + P[r_1-1][c_1-1] $$
겹쳐 뺀 왼쪽 위 모서리를 다시 더해 주는 것이 포인트입니다.
5. 차이 배열: 누적 합의 쌍대
반대로 "여러 구간에 일괄로 값을 더하고, 마지막에 한 번 결과를 본다" 면
차이 배열(difference array) 을 씁니다. 구간 \([l, r]\)에 \(v\)를 더할 때
diff[l] += v; diff[r+1] -= v;만 하고, 마지막에 diff의 누적 합을 취하면 됩니다.
각 구간 갱신이 \(O(1)\), 마지막 복원이 \(O(N)\)입니다. 누적 합과 차이 배열은
서로 역연산 관계입니다.
정리
누적 합은 "구간 합 = 두 누적 합의 차"라는 한 줄짜리 아이디어로 구간 질의를
\(O(1)\)에 답합니다. 1-인덱스로 짜면 깔끔하고, 2차원·차이 배열로 자연스럽게
확장됩니다. 다음 강의에서 구현과 응용을 다룹니다.