---
title: "누적 합: 구간 전체를 다시 더하지 않는 전처리"
author: "Lee"
published_at: "2026-10-16T17:51:03.862Z"
updated_at: "2026-09-30T09:50:28.132Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%88%84%EC%A0%81-%ED%95%A9-%EA%B5%AC%EA%B0%84-%EC%A0%84%EC%B2%B4%EB%A5%BC-%EB%8B%A4%EC%8B%9C-%EB%8D%94%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-%EC%A0%84%EC%B2%98%EB%A6%AC"
ai_assisted: false
---

# 누적 합: 구간 전체를 다시 더하지 않는 전처리

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%88%84%EC%A0%81-%ED%95%A9-%EA%B5%AC%EA%B0%84-%EC%A0%84%EC%B2%B4%EB%A5%BC-%EB%8B%A4%EC%8B%9C-%EB%8D%94%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-%EC%A0%84%EC%B2%98%EB%A6%AC)

누적 합은 배열 시작부터 각 위치까지의 합을 미리 저장하는 방법이다. 같은 배열에서 여러 구간 합을 묻는다면 구간마다 다시 순회할 필요가 없다. 한 번의 O(n) 전처리로 이후 질의를 O(1)에 처리한다.

![배열 2·1·3·4의 누적 합 0·2·3·6·10에서 6에서 2를 빼 구간 합 4를 구하는 과정](/api/v1/media/61321210-a2d3-4004-acd7-c0f2ce3a6cff)

*맨 앞에 0을 둔 누적 합에서는 구간 양 끝 경계의 값을 빼면 된다.*

### 빈 접두 구간을 먼저 둔다

P[0]=0, P[i+1]=P[i]+A[i]로 정의하면 P[i]는 원소 i개, 즉 [0,i)의 합이다. 따라서 반열린 구간 [l,r)의 합은 P[r]-P[l]이다. 끝 인덱스를 포함하는 방식과 섞지 않아야 한다.

```python
def build_prefix(values):
    prefix = [0] * (len(values) + 1)
    for index, value in enumerate(values):
        prefix[index + 1] = prefix[index] + value
    return prefix

def range_sum(prefix, left, right):
    if not 0 <= left <= right < len(prefix):
        raise ValueError("Invalid half-open range")
    return prefix[right] - prefix[left]

values = [3, -2, 5, 1]
prefix = build_prefix(values)
# prefix is [0, 3, 1, 6, 7]
# values[1:3] has sum prefix[3] - prefix[1] = 3
```

음수 원소가 있어도 덧셈과 뺄셈의 관계는 그대로 성립한다. l=r인 빈 구간은 0이 된다. 0을 앞에 넣지 않고 특별한 첫 구간 조건을 붙일 수도 있지만 인덱스 분기가 늘어난다.

### 빼기 가능한 집계라는 조건

전체 앞부분 P[r]에서 원하지 않는 앞부분 P[l]을 제거하면 남은 구간만 남는다. 합의 역연산이 빼기라서 가능한 일이다. XOR도 같은 구조를 사용할 수 있지만 최솟값은 앞부분 최솟값을 빼서 뒤 구간 최솟값을 얻을 수 없다.

질의가 q개라면 단순 순회는 최악 O(nq), 누적합은 O(n+q)다. 저장 공간은 O(n)이며 원본 배열을 그대로 보관할지는 별도 선택이다. 질의가 하나뿐이거나 입력이 스트리밍이라면 전처리의 이점이 다를 수 있다.

배열 원소 하나를 바꾸면 그 위치 뒤의 모든 누적값이 달라질 수 있다. 기본 누적합은 갱신에 O(n)이 필요하므로 빈번한 점 갱신에는 펜윅 트리나 세그먼트 트리가 적합하다. 질의가 빠르다는 장점은 데이터가 고정적일 때 특히 크다.

2차원 누적합은 왼쪽 위 직사각형 합을 저장한다. 원하는 사각형은 큰 접두 사각형에서 위쪽과 왼쪽을 빼고 두 번 뺀 겹침을 한 번 더하여 얻는다. 포함·배제 원리를 구현한 것이다.

합이 커지면 정수 오버플로를 확인해야 하고 부동소수점 누적은 반올림 오차가 생길 수 있다. 구간 표현, 수치 범위, 데이터 변경 빈도를 명시하면 짧은 공식이 실용적인 자료 처리 도구가 된다.

앞부분의 합이 작아도 두 큰 누적값의 차이를 구할 때 부동소수점 유효 자릿수를 잃을 수 있다. 정확한 정수 합과 근사 실수 합은 수치적 성질이 다르다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)