Fenwick Tree는 배열에서 구간 합과 값 갱신을 빠르게 처리하기 위한 자료구조다.
Binary Indexed Tree라고도 부른다.
예를 들어 다음 배열이 있다고 하자.
arr = [3, 2, 5, 1, 4]이 배열에서 다음 질문이 반복해서 들어올 수 있다.
1번부터 4번까지의 합은?
2번부터 5번까지의 합은?
3번 값이 바뀌면 이후 합은?값이 고정되어 있다면 prefix sum 배열만으로도 구간 합을 빠르게 구할 수 있다. 하지만 중간 값이 자주 바뀌면 prefix sum 배열을 다시 계산해야 한다.
Fenwick Tree는 이 문제를 해결하기 위해 누적 합을 여러 작은 구간 합 조각으로 나눠 저장한다.
Prefix Sum은 누적 합 배열이다.
arr = [3, 2, 5, 1, 4]
prefix = [3, 5, 10, 11, 15]구간 합은 빠르게 구할 수 있다.
sum(2~4) = prefix[4] - prefix[1]하지만 배열 값이 바뀌면 이후 prefix 값을 모두 다시 계산해야 한다.
arr[2]가 바뀜
-> prefix[2], prefix[3], prefix[4], prefix[5] 모두 영향즉 prefix sum은 조회는 빠르지만, 값 변경이 자주 일어나는 상황에서는 갱신 비용이 커진다.
Fenwick Tree의 각 인덱스는 전체 합이 아니라 자신이 담당하는 부분 구간의 합을 저장한다.
말로 설명하면 다음과 같다.
누적 합을 통째로 저장하지 않고,
여러 구간 합 조각으로 나눠 저장한다.
합을 구할 때는 필요한 조각들을 모아서 더한다.
값이 바뀌면 영향을 받는 조각만 다시 갱신한다.어떤 위치는 자기 자신만 담당하고, 어떤 위치는 앞의 2개, 4개, 8개처럼 더 큰 구간을 담당한다.
이 구조 덕분에 prefix sum 조회와 값 갱신을 모두 O(log N)에 처리할 수 있다.
Fenwick Tree를 코드나 이진수 없이 설명하면 이렇게 말할 수 있다.
많은 숫자의 합을 매번 처음부터 더하지 않기 위해,
미리 작은 구간 합들을 여러 조각으로 저장해 둔다.
합을 물어보면 필요한 조각만 골라 더하고,
숫자가 바뀌면 관련된 조각만 수정한다.즉 Fenwick Tree는 “전체 합을 빠르게 만들기 위한 부분 합 조각 저장 방식”이다.
Fenwick Tree는 내부적으로 인덱스의 이진수 표현을 이용해 각 위치가 담당하는 구간 크기를 결정한다.
이때 사용하는 값이 lowbit이다.
lowbit(i) = i & -ilowbit은 인덱스에서 가장 낮은 위치의 1-bit가 나타내는 값을 구한다.
예를 들어 어떤 인덱스가 4개짜리 구간을 담당하는지, 2개짜리 구간을 담당하는지 판단하는 데 사용한다.
하지만 개념 설명에서는 수식보다 다음 문장이 더 중요하다.
인덱스의 이진수 정보를 이용해
각 위치가 담당하는 구간 크기를 정하고,
필요한 구간만 건너뛰며 더하거나 갱신한다.| 작업 | 시간 복잡도 |
|---|---|
| prefix sum 조회 | O(log N) |
| 특정 값 갱신 | O(log N) |
| 구간 합 조회 | O(log N) |
구간 합은 보통 prefix sum 두 개의 차이로 구한다.
sum(left~right) = prefixSum(right) - prefixSum(left - 1)Fenwick Tree와 Segment Tree는 둘 다 구간 쿼리를 처리할 수 있는 자료구조다.
| 구분 | Fenwick Tree | Segment Tree |
|---|---|---|
| 주 용도 | prefix sum, 구간 합, 빈도 누적 | 다양한 구간 질의 |
| 구현 난이도 | 비교적 간단 | 더 복잡 |
| 메모리 | 적게 사용 | 더 많이 사용 |
| 확장성 | 제한적 | 높음 |
Fenwick Tree가 적합한 경우는 다음과 같다.
- prefix sum
- 구간 합
- 빈도 누적
- 값 하나 업데이트
- 누적 가능한 단순 연산
Segment Tree가 더 적합한 경우는 다음과 같다.
- 구간 최솟값
- 구간 최댓값
- 구간 gcd
- 구간 업데이트
- lazy propagation
- 복잡한 구간 질의
즉 Fenwick Tree는 단순한 누적 합 문제에 가볍고 빠른 선택지이고, Segment Tree는 더 복잡한 구간 연산에 유리하다.
Fenwick Tree는 배열의 값이 바뀌는 상황에서도 prefix sum과 구간 합을 빠르게 구하기 위한 자료구조다.
핵심은 전체 누적 합을 그대로 저장하는 것이 아니라, 부분 구간 합을 여러 조각으로 나눠 저장하는 것이다.
말로 설명할 때는 다음처럼 정리할 수 있다.
Fenwick Tree는 구간 합을 빠르게 구하기 위해
부분 합 조각들을 저장해 두고,
필요한 조각만 더하거나 갱신하는 자료구조다.