에듀테크 프로젝트 대시보드
펜윅 트리 (Binary Indexed Tree)
누적 합 배열은 질의가 O(1)이지만 수정이 O(n) — 펜윅 트리는 i & -i 비트 트릭 한 줄로 갱신·질의 둘 다 O(log n)
"1번부터 k번까지 점수의 합"을 자주 구해야 한다고 하자. 누적 합(prefix sum) 배열을 미리 만들면
질의는 P[k] 한 번으로 O(1)이다. 그런데 중간에 한 값이 바뀌면 그 뒤 누적 합을
전부 다시 계산해야 해서 수정이 O(n)이 된다.
펜윅 트리는 크기 n짜리 배열 T 하나로 이 문제를 푼다.
T[i]는 구간 [i - lowbit(i) + 1, i]의 부분합을 담는다.
여기서 lowbit(i) = i & -i는 i의 이진수에서 가장 낮은 1비트의 값이다.
이 규칙 덕분에 갱신도 질의도 비트를 따라 O(log n)번만 움직이면 끝난다. 세그먼트 트리보다 코드가
훨씬 짧고 상수도 작아서 대회에서 즐겨 쓰인다.
2의 보수에서 -i는 ~i + 1이다. 그래서 i와
-i를 AND하면 맨 아래 켜진 비트 하나만 살아남는다. 슬라이더를 움직여 확인해 보자.
아래는 n = 8일 때 각 T[i]가 책임지는 원소 구간이다.
길이는 정확히 lowbit(i). 8은 [1..8] 전체를, 홀수 인덱스는 자기 자신 하나만 덮는다.
위쪽 A 칸을 클릭하면 값이 1 늘고(9 다음은 0), update가
i += lowbit(i)로 보라색 경로를 타고 올라가며
아래 T 칸들을 고친다. 슬라이더로 k를 정하고 접두사 합 query(k)를 누르면
k -= lowbit(k)로 내려가며 초록색 T 칸들을 더해 A[1..k] 합을 만든다.
update는 매번 i += lowbit(i)로 자기보다
큰, 더 높은 비트 쪽으로 점프한다. 매 단계 최소 1비트가 위로 올라가므로 최대 log₂ n번이면
n을 넘는다. query는 반대로 k -= lowbit(k)로
켜진 비트를 하나씩 끄며 0으로 간다. 켜진 비트 수만큼만 도니까 역시 O(log n).
# 1-indexed. T는 크기 n+1, 전부 0으로 시작 def lowbit(i): return i & -i # 가장 낮은 1비트 def update(i, delta): # A[i] 에 delta 더하기 while i <= n: T[i] += delta i += lowbit(i) # 나를 포함하는 다음 구간으로 def query(k): # A[1] + ... + A[k] s = 0 while k > 0: s += T[k] k -= lowbit(k) # 켜진 비트 하나 끄기 return s def range_sum(l, r): # A[l] + ... + A[r] return query(r) - query(l - 1)
update하면 O(n log n)이지만,
T[i] += A[i] 후 j = i + lowbit(i)가 범위 안이면
T[j] += T[i]를 해 주면 전체 O(n)에 만들 수 있다.
| 항목 | 세그먼트 트리 | 펜윅 트리 (BIT) |
|---|---|---|
| 메모리 | ≈ 2n ~ 4n | 정확히 n (+1) |
| 코드 길이 | 길다 (재귀/반복) | 3~4줄 |
| 지점 갱신 · 접두사 합 | O(log n) | O(log n), 상수 더 작음 |
| 구간 최솟값/최댓값 | 가능 | 기본형은 불가 (합·XOR 등 역연산 필요) |
| 구간 갱신 + 구간 질의 | lazy propagation | BIT 2개로 확장 |
| 임의 구간 질의 | 바로 가능 | query(r) - query(l-1) |