누적합과 세그먼트 트리
같은 배열에서 구간 합을 구하고 값 하나를 바꿨을 때 다시 계산하는 범위를 비교합니다
개요
여러 번 구간 합을 구해야 할 때는 합을 미리 저장해 둘 수 있습니다. 누적합은 배열 앞부분의 합을 한 줄에 저장하고, 세그먼트 트리는 배열을 나눈 여러 구간의 합을 트리에 저장합니다. 이 차이는 원본 배열의 값이 바뀔 때 드러납니다.
누적합으로 조회하기
배열의 인덱스는 0부터 시작합니다. 누적합 P[i]에는 앞에서부터 원소 i개의 합을 저장합니다. P[0] = 0에서 시작해 P[i + 1] = P[i] + A[i]로 다음 칸을 채웁니다.
양끝을 포함하는 [L, R]의 합은 P[R + 1] − P[L]입니다. 예제 배열 [4, 2, -1, 5, 3, 6, -2, 7]에서 [1, 6]의 합은 P[7] − P[1] = 17 − 4 = 13입니다.
세그먼트 트리로 조회하기
리프는 배열 원소 하나를 저장합니다. 부모는 서로 겹치지 않는 두 자식 구간의 합을 저장합니다. 루트에서 시작해 노드의 구간을 조회 범위와 비교합니다.
- 조회 범위에 완전히 들어가는 노드는 저장된 합을 더하고 그 아래는 탐색하지 않습니다.
- 조회 범위와 겹치지 않는 노드는 건너뜁니다.
- 일부만 겹치면 두 자식 구간을 확인합니다.
예제에서는 [1, 1], [2, 3], [4, 5], [6, 6]의 합을 더합니다. 네 구간이 겹치지 않으면서 [1, 6]을 빠짐없이 덮으므로 2 + 4 + 9 + (-2) = 13입니다. 트리에서 리프의 구간은 [i]로 줄여 표시합니다.
값 하나를 바꾸면
A[2]를 -1에서 4로 바꾸면 차이는 +5입니다. 누적합에서는 인덱스 2를 포함하는 P[3]부터 P[8]까지 6칸에 차이를 더합니다. 트리에서는 리프 [2, 2]와 그 조상 [2, 3], [0, 3], [0, 7]까지 4개 노드만 다시 계산합니다. 두 방식 모두 갱신 후 [1, 6]의 합은 18입니다.
연산별 복잡도
| 연산 | 누적합 | 세그먼트 트리 |
|---|---|---|
| 초기 구성 | O(n) | O(n) |
| 구간 합 조회 | O(1) | O(log n) 최악 |
| 원소 한 개 갱신 | O(n) 최악 | O(log n) |
| 추가 공간 | O(n) | O(n) |
월별 매출처럼 원본을 고정해 두고 조회가 많은 데이터에는 누적합이 간단합니다. 개별 기록이 자주 바뀌고 구간 합도 계속 조회한다면 세그먼트 트리가 갱신 범위를 줄여 줍니다.
학습 목표
- 양끝을 포함한 [L, R]의 합을 두 누적합으로 계산할 수 있다.
- 트리 노드를 완전히 포함, 일부 겹침, 범위 밖으로 구분할 수 있다.
- 한 원소를 바꿨을 때 갱신하는 누적합 칸과 트리 노드를 설명할 수 있다.
자주 하는 오해
- P[i]는 A[i] 직전까지의 합이므로 오른쪽 끝 R을 포함하려면 P[R + 1]을 사용합니다.
- 트리에서 부모의 합을 더했다면 그 자식의 합은 중복해서 더하지 않습니다.
핵심 정리
- 누적합은 두 칸만 읽어 구간 합을 구합니다. 값이 바뀌면 그 값을 포함하는 뒤쪽 칸들을 갱신합니다.
- 세그먼트 트리는 조회 범위를 겹치지 않는 노드로 덮고, 한 원소가 바뀌면 해당 리프의 조상만 다시 계산합니다.
학습 확인
핵심 단계
- 1
누적합은 0에서 시작해 원소를 하나씩 더하고, 트리는 리프를 채운 뒤 아래에서 위로 합을 저장합니다.
- 2
같은 [1, 6]을 누적합에서는 두 칸의 차이로 구하고, 트리에서는 완전히 포함된 구간들의 합으로 구합니다.
- 3
A[2]를 바꿔 누적합의 뒤쪽 칸과 트리의 리프부터 루트까지 갱신합니다.
- 4
갱신 후 같은 구간을 다시 조회해 두 방식의 결과를 비교합니다.
핵심 개념 및 실무 적용 분야
참고 자료
개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.