Binary Indexed Tree(Fenwick tree ; 펜윅트리)

LSB

본격적인 Binary Indexed Tree를 설명하기에 앞서 LSB(k)에 대해 간단히 알아보자. (나중에 쓰이는 연산임!)

어떤 수 k를 2진수로 바꿨을 때 가장 첫 번째로 1이 등장하는 위치를 d라 하자. LSB(k) = 2^d 를 말한다. 아래의 예시를 보면 이해에 도움이 될 것이다.

 

LSB(10) 

10 = 1010(2진수)

가장 첫 번째로 1이 등장하는 위치 d = 1 (오른쪽부터 0으로 카운트 시작)

LSB(10) = 2^1 = 2

 

LSB(12) 

12 = 1100

d = 2

LSB(12) = 2^2 = 4

 

LSB(8)

8 = 1000

d = 3

LSB(8) = 2^3 = 8

 

 LSB 빠르게 구하기

실제 코드에서 LSB(k)를 상수시간 내 계산하는 방법은 -k(2의 보수)를 활용하는 것이다.

* 2의 보수는 1의 보수(비트 역전) + 1과 같다.

 

결론부터 정리하자면 LSB(k) = k&-k와 같다. 아래 예시를 살펴보자.

 

ex. k = 01101000

-k = 10010111 + 1 = 10011000

k & -k = 01101000 & 10011000 = 0001000 = 8

LSB(k) = 2^3 = 8

prefix_sum(구간합)

Binary Indexed Tree 리스트(배열)을 만들 때는 prefix_sum(구간합)이 사용된다.

 

어떤 리스트 A를 입력으로 받은 후, 인덱스가 1부터 시작된다고 가정하자.

 

prefix_sum(k) = A[1] + .... + A[k]

즉 prefix_sum(k)은 배열 A에서 인덱스1부터 k까지 모든 원소의 합을 말한다.

binary indexed tree

본격적으로 binary indexed tree를 알아보자.

 

binary indexed tree는 prefix_sum 연산을 빠르게 제공하는 자료구조이다. 어떤 리스트 A에 대한 binary indexed tree를 T라고 했을 때, T[k] = A[k] + ... + A[k - LSB(k) +1]로 구성된다.

 

즉, T[k]에는 인덱스 k에서부터 k-LSB(k)+1까지 총 LSB(k)개의 A 원소를 더한 값과 같다고 할 수 있다. 이를 그림으로 나타내면 다음과 같다.

 

 

 

BIT를 활용한 prefix_sum 연산

<pseudo code>

def prefix_sum(k) :
	s = 0 # 결과 저장 변수
    while k >= 1 : # k의 최소 인덱스는 1
    	s = s + T[k]
        k = k - LSB(k)
    return s

Update 연산

오리지널 입력 리스트 A가 변경된다면 BIT인 리스트 T는 어떻게 바뀔까? 

<pseudo code>

def update(k,x) : # A[k] -> x로 update
	d = x - A[k] # update된 정도
    while k <= n :
    	T[k] = T[k] + d
        k = k + LSB(k)

시간 복잡도 : while 문을 도는 횟수는 최대 비트수와 같으므로 O(log n)

 

정리

Binary Indexed Tree ; BIT

1. 전처리 과정을 통해서 Binary Indexed Tree를 O(n) 시간 내 구성 가능

2. 질의(prefix_sum, update) 연산을 모두 O(log n) 시간 내 가능

 

 

---

* 본 포스팅은 신찬수 교수님의 유튜브 강의를 요약하여 작성되었습니다. 

* 포스팅에 사용된 이미지는 직접 제작하였습니다.

https://youtu.be/hUjaxK9zx5M