바이너리 인덱스 트리

(이거 지금은 무슨 소리인지 이해 안 감)

 

 

 

2진법에서 모든 비트에 대해서 플립(0을 1로, 1을 0으로)을 진행하고 1을 더하면 7에서 -7이 된다

바이너리 인덱스 트리에서는 "0이 아닌 마지막 비트를 찾는 과정"이 효과적으로 사용된다

 

 

 

3
3 + 1 = 4
3 + 1 + 4 = 8
3 + 1 + 4 + 8 = 16

 

데이터의 개수가 N개일 때 특정 위치의 값을 바꿀때 최악의 경우에도 logN을 보장한다