prefix sum이란 무엇이며 어떻게 범위 질의를 빠르게 하나요?

Question

Accepted Answer

**Prefix sum(누적 합)** 배열은 누적 합계를 저장하여, O(n) 전처리 후 어떤 **범위 합**이든 **O(1)**에 답할 수 있게 합니다 — 질의당 O(n) 대신입니다.

## 개념

`prefix[i]`를 처음 `i`개 원소의 합이라고 합시다. 그러면 `arr[l..r]`의 합은 `prefix[r+1] - prefix[l]`입니다.

## 예시

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # 누적 합계
    return prefix

def range_sum(prefix, l, r):            # 양 끝 포함 l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## 추적

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## 복잡도

- **구축:** O(n). **질의:** O(1). **공간:** O(n).

## 언제 사용하나 / 함정

정적 데이터에 대한 **다수의 범위 합 질의**에 이상적입니다. 변형: 부분 행렬 합을 위한 2D prefix sum, prefix XOR, 범위 갱신을 위한 difference array. 배열이 자주 바뀌면 대신 Fenwick/segment tree를 사용하세요. 인덱스 오프셋(크기 n+1)을 주의하세요.

## 왜 중요한가

Prefix sum은 반복되는 O(n) 범위 질의를 O(1) 조회로 바꿉니다 — 질의가 잦을 때 큰 이득입니다.

한 번 미리 계산하고 빠르게 답하는 패턴은 많은 데이터 처리 작업으로 일반화됩니다.

경쟁 프로그래밍의 필수 요소이며 분석에서 흔한 빌딩 블록입니다.