📚 Reference

📜 Chapter

Fenwick Tree

Fenwick Tree
Binary Indexed Tree
BIT
펜윅 트리
데이터의 변경과 구간 합(Prefix Sum) 계산을 모두 아주 빠르게 해결하기 위해 고안된 자료구조이다.

배열, 누적 합, Fenwick - 비교

방식	구간 합 구하기	값 업데이트하기	특징
일반 배열	O(N) (다 더해야 함)	O(1) (그냥 바꿈)	합 구하기가 너무 느림
누적 합 배열	O(1) (미리 계산됨)	O(N) (이후 합 다 수정)	데이터 변경이 너무 느림
Fenwick Tree	O(log N)	O(log N)	둘 다 빠름!

원리: 2진수의 마법

Fenwick Tree의 핵심은 "모든 숫자는 2의 거듭제곱의 합으로 표현된다"는 점을 이용하는 것이다.
예를 들어, 7번 인덱스까지의 합은 7 = 4 + 2 + 1로 쪼갤 수 있다.
Fenwick Tree의 각 노드는 자신이 담당하는 특정 구간의 합을 가지고 있고, 우리는 이진수 비트 연산을 통해 필요한 구간들만 골라 "점프"하며 합을 구한다.