누적 합 (Prefix Sum)

정의

누적 합 (Prefix Sum) 은 배열 a[0..N-1] 에 대해 S[i] = a[0] + a[1] + ... + a[i-1] (또는 1-indexed S[i] = a[1] + ... + a[i]) 을 미리 계산해 두고, 임의 구간 합 a[l..r] 을 O(1) 에 구하는 정형.

sum(l, r) = S[r + 1] - S[l]

문제 풀이에서 “구간 N 개 × Q 개 쿼리” 가 O(N + Q) 로 떨어지는 가장 기본 패턴.

문제 상황과 동기

Σ a[l..r] 을 Q 번 묻는다.

• naive: 매 쿼리마다 l..r 순회. O(N · Q). N=Q=10^5 면 10^10, 절대 안 됨.
• prefix sum: O(N) 전처리 + O(1) 쿼리. 총 O(N + Q).

핵심 통찰: 합 함수 S(x) 를 한 번만 계산하면, 임의 구간은 두 점의 차. 누적은 도함수 / 미분이 가능한 모든 연산에 일반화 (XOR, AND/OR, min/max 같은 단조 연산은 누적 가능 / 불가능).

시각화

핵심 아이디어

invariant: S[i] = 처음 i 개 원소의 합. 두 누적 합의 차 가 구간 합.

S[0] = 0
S[i] = S[i-1] + a[i-1]   for i = 1..N

sum(l, r) (0-indexed, inclusive)
  = a[l] + a[l+1] + ... + a[r]
  = S[r+1] - S[l]

확장:

• 2D prefix sum: S[i][j] = Σ_{i' ≤ i, j' ≤ j} a[i'][j']. 구간 사각형 합 O(1).
• 차분 배열 (difference array): prefix sum 의 역. 구간 갱신 O(1) + 끝에 한번 누적.
• mod prefix: mod 가 있을 때 음수 조심.
• XOR prefix: 덧셈 대신 XOR. 구간 XOR 도 O(1).

알고리즘

build_prefix(a):
    S[0] = 0
    for i = 1..N:
        S[i] = S[i-1] + a[i-1]

range_sum(l, r):    # 0-indexed inclusive
    return S[r+1] - S[l]

구현

// 1D prefix sum, O(N) 전처리 + O(1) 쿼리
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, q; cin >> n >> q;
  vector<long long> a(n), S(n + 1, 0);
  for (auto& v : a) cin >> v;
  for (int i = 1; i <= n; i++) S[i] = S[i-1] + a[i-1];
  while (q--) {
      int l, r; cin >> l >> r;          // 1-indexed [l, r]
      cout << S[r] - S[l-1] << "\n";
  }
}

# itertools.accumulate 로 O(N) 한 줄 prefix sum
from itertools import accumulate
import sys
input = sys.stdin.readline
​
n, q = map(int, input().split())
a = list(map(int, input().split()))
S = [0] + list(accumulate(a))
out = []
for _ in range(q):
  l, r = map(int, input().split())     # 1-indexed [l, r]
  out.append(str(S[r] - S[l-1]))
print("\n".join(out))

// long 으로 합. 큰 N 의 합 오버플로우 방지
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int q = Integer.parseInt(st.nextToken());
      long[] S = new long[n + 1];
      st = new StringTokenizer(br.readLine());
      for (int i = 1; i <= n; i++)
          S[i] = S[i-1] + Long.parseLong(st.nextToken());
      StringBuilder sb = new StringBuilder();
      while (q-- > 0) {
          st = new StringTokenizer(br.readLine());
          int l = Integer.parseInt(st.nextToken());
          int r = Integer.parseInt(st.nextToken());
          sb.append(S[r] - S[l-1]).append('\n');
      }
      System.out.print(sb);
  }
}

5 3
1 2 3 4 5
1 3
2 4
1 5

6
9
15

복잡도

2D 누적 합

S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]

rect_sum(r1, c1, r2, c2)
  = S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]

inclusion-exclusion 한 단계.

변형

함정

1. 1-indexed vs 0-indexed

sum(l, r) 에서 S[r] - S[l-1] (1-indexed) 와 S[r+1] - S[l] (0-indexed) 둘 다 자주 헷갈림. 한 표기 일관성 있게.

2. 합 오버플로우

C++ 에서 N=10^5 이상이면 합이 long long 범위 필요. int 누적은 위험.

3. 음수 mod

(S[r] - S[l-1]) % MOD 가 음수가 될 수 있다. + MOD 후 다시 mod.

4. 갱신 빈도

원소 갱신이 잦으면 prefix sum 은 매번 재계산 (O(N)) 비용. 그 경우 세그먼트 트리 또는 Fenwick.

BOJ 연습 문제

참고

• 차분 배열
• 두 포인터
• 슬라이딩 윈도우
• 세그먼트 트리 (갱신 잦을 때)