바이너리 인덱스 트리 (BIT, Binary Indexed Tree) 정의

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

바이너리 인덱스 트리 (BIT, Binary Indexed Tree)

데이터 업데이트가 가능한 상황에서의 구간 합 (Interval Sum)
 

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 
그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 
3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다.
그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면12가 될 것이다.


 바이너리 인덱스 트리 사용
  2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있는 자료구조를 의미.
  == 펜윅 트리(fenwick tree) 라고도 함.
 

 0이 아닌 마지막 비트를 찾는 방법
  특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 K & -K를 계산하면 된다.

n=8

for i in range (n+1):
	print(i, "의 마지막 비트:", (i & -i))

하면 일치하게 됨.

 

 바이너리 인덱스 트리 :
 > 트리 구조 만들기 : 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수
 > 업데이트 : 0이 아닌 마지막 비트만큼 더하면서 구간들의 값을 변경 (예시 = 3rd)
   최악의 경우를 가정하여도 시간 복잡도는 logN 을 보장함.
 > 누적 합 구하기 : 0이 아닌 마지막 비트만큼 빼면서 구간들의 값의 합 계산 (예시 = 11th)
   최악의 경우도 logN의 시간 복잡도를 보장함.

 

 

---