개념
합 배열을 이용해 구간 합의 시간 복잡도를 O(N)에서 O(1)로 줄이는 알고리즘
핵심 이론
1. 합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i] // A[0]부터 A[i]까지의 누적합2. 합 배열 생성 공식
S[i] = S[i-1] + A[i]3. 구간 합 계산 공식
A[i]부터 A[j]까지의 합 = S[j] - S[i-1]예제
원본 배열
A = [3, 6, 5, 10, 4]합 배열 생성
S[0] = 3
S[1] = 3 + 6 = 9
S[2] = 9 + 5 = 14
S[3] = 14 + 10 = 24
S[4] = 24 + 4 = 28
결과: S = [3, 9, 14, 24, 28]구간 합 계산 예시
A[2]부터 A[4]까지의 합을 구하려면:
- 직접 계산: 5 + 10 + 4 = 19
- 구간 합 활용:
S[4] - S[1] = 28 - 9 = 19
장점
- 시간 복잡도: O(1)로 빠른 계산
- 효율성: 여러 구간 쿼리를 반복 처리할 때 유용
- 전처리: 한 번만 합 배열을 생성하면 됨
핵심 아이디어
큰 구간의 누적합에서 작은 구간의 누적합을 빼면 특정 구간의 합을 구할 수 있다.
Q 배열의 값이 자주 바뀌면?
구간 합의 한계
배열 값이 자주 변경되는 경우:
- 값이 바뀔 때마다 합 배열 S를 전체 재계산 해야 함
- 시간 복잡도: O(N) (비효율적)
해결책
1. Segment Tree (세그먼트 트리)
- 구조: 완전 이진 트리
- 업데이트: O(log N)
- 구간 합 쿼리: O(log N)
- 특징: 구간 합뿐만 아니라 최솟값, 최댓값 등 다양한 연산 지원
2. Fenwick Tree (펜윅 트리, Binary Indexed Tree)
- 구조: 배열 기반의 트리 구조
- 업데이트: O(log N)
- 구간 합 쿼리: O(log N)
- 특징: 세그먼트 트리보다 메모리 효율적, 구현이 간단