Range Sum (or Prefix Sum)

Range Sum (구간 합)

개념

합 배열을 이용해 시간 복잡도를 **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

장점

1. 시간 복잡도: O(1)로 빠른 계산
2. 효율성: 여러 구간 쿼리를 반복 처리할 때 유용
3. 전처리: 한 번만 합 배열을 생성하면 됨

핵심 아이디어

큰 구간의 누적합에서 작은 구간의 누적합을 빼면 특정 구간의 합을 구할 수 있다.

---

Q 배열의 값이 자주 바뀌면?

구간 합의 한계

배열 값이 자주 변경되는 경우:

• 값이 바뀔 때마다 합 배열 S를 전체 재계산 해야 함
• 시간 복잡도: O(N) (비효율적)

해결책

1. Segment Tree (세그먼트 트리)

• 구조: 완전 이진 트리
• 업데이트: O(log N)
• 구간 합 쿼리: O(log N)
• 특징: 구간 합뿐만 아니라 최솟값, 최댓값 등 다양한 연산 지원

2. Index Tree (인덱스 트리) = Fenwick Tree

• 구조: 배열 기반의 트리 구조
• 업데이트: O(log N)
• 구간 합 쿼리: O(log N)
• 특징: 세그먼트 트리보다 메모리 효율적, 구현이 간단

---

Next

Stack and Queue