펜윅 트리 (BIT) 시각화
바이너리 인덱스 트리의 누적합 업데이트와 구간 쿼리를 O(log n)으로 처리하는 과정을 학습하세요
자료구조★★☆
속도
1 / 1원본 배열: [3, 2, 5, 1, 7, 4, 6, 8]
연산 선택
현재방문업데이트
lowbit(i) = i & (-i)
담당 구간: BIT[i] → arr[i - lowbit(i) + 1 .. i]
펜윅 트리의 업데이트·쿼리 과정에서 lowbit 연산을 관찰하세요.
연산을 선택하고 실행을 눌러 시작하세요.
펜윅 트리란?
비트 연산을 활용하여 누적합 갱신과 쿼리를 O(log n)에 수행하는 간결한 자료구조입니다. Binary Indexed Tree(BIT)라고도 합니다.
사용 방법
- 1배열을 생성하면 BIT가 자동으로 구축됩니다
- 2특정 인덱스의 값을 변경하면 BIT 업데이트 과정을 볼 수 있습니다
- 3누적합 쿼리로 1~i까지의 합을 구하는 과정을 확인하세요
- 4이진 표현을 보며 lowbit 연산의 패턴을 관찰하세요
동작 원리
- 1각 인덱스 i는 lowbit(i) = i & (-i) 크기만큼의 구간을 담당합니다
- 2업데이트: 인덱스에 lowbit를 더하며 상위 노드를 갱신합니다
- 3쿼리: 인덱스에서 lowbit를 빼며 구간합을 누적합니다
- 4구간합 [l, r] = prefixSum(r) - prefixSum(l-1)로 계산합니다
실무 활용
- •경쟁 프로그래밍의 구간합/역수 카운팅 문제
- •실시간 순위 계산(BIT + 좌표 압축)
- •2D BIT로 직사각형 영역 합 쿼리
- •온라인 판사 시스템의 채점 통계
비슷한 알고리즘
- •세그먼트 트리 — 더 범용적이나 메모리 2배, 구현 복잡
- •누적합 배열 — O(1) 쿼리이나 업데이트가 O(n)
- •sqrt 분할 — 구현 단순하나 O(√n) 성능
학습 팁
- •lowbit(i) = i & (-i)가 핵심 — 이진수 끝 1의 위치를 반환합니다
- •인덱스를 이진수로 변환하며 담당 구간 패턴을 파악하세요
- •세그먼트 트리와 비교하며 장단점을 정리해보세요
자주 묻는 질문
Q. lowbit란?
A. i & (-i)로 인덱스의 최하위 비트를 추출합니다. 이것이 담당 구간 크기가 됩니다.
Q. 0-indexed 배열에서도 사용 가능?
A. BIT는 1-indexed가 자연스럽습니다. 0-indexed라면 인덱스에 1을 더해 사용합니다.