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

( 강의 출처 : https://www.youtube.com/watch?v=fg2iGP4e2mc&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=14&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 )

 : 바이너리 인덱스 트리 ( Binary Index Tree, BIT )
     펜윅 트리라고도 한다.

 : 데이터의 업데이트가 가능한 상황에서의 구간 합

     ( BOJ 문제 : https://www.acmicpc.net/problem/2042 )
     어떤 상황을 의미하냐면,
     1,2,3,4,5 가 있을때, 

     3번째 숫자를 6으로 바꾸고 
     2번째부터 5번째 수의 합을 구하면 17이 된다.
 
     그리고 5번째 숫자를 2로 바꾸고
     3번째부터 5번째 수의 합을 구하면 12가 된다.

     데이터 개수 : N ( 1 <= N <= 1000000 )
     데이터 변경 횟수 : M ( 1 <= M <= 10000)
     구간 합 계산 횟수 : K ( 1 <= K <= 10000)

     이러한 상황을 말한다.
     M과 K는 같지 않을까 싶지만, 무튼 그러하다.
     문제 링크에 찾아가보니 명확한 표시를 위해 K를 따로 변수로 둔 것 같다.

     우선 떠오르는 방법으로는
     이전에 배웠던 구간합
     ( https://the-bingle.tistory.com/89 )
     을 이용하면 될 것 같은데, 

     바이너리 인덱스 트리를 이용해서 해결하는 편이 더 좋다고 한다.
     우선 보도록 하자.


 : 특정 수 i의 0이 아닌 마지막 비트를 찾기.

     만약 i==7 일때
     비트 단위로 표시하면

     i : 00000000 00000000 00000000 00000111
     -i : 11111111 11111111 11111111 11111001

     이 된다. 

     & 연산자는 비트연산자로 대응되는 두 비트가 둘 모두 1일때 1이된다.
     ( 1 & 1 = 1
      1 & 0 = 0
      0 & 0 = 1 
     AND연산을 생각하면 된다. )

     
 : 이렇게 0이 아닌 마지막 비트를 구했다면, 이 값을 내가 저장하고 있는 값들의 개수로 보자.

     이후 특정 값을 변경할 때 0이 아닌 마지막 비트만큼 더하면서 구간들의 값을 변경하여
     업데이트를 수행할 수 있다. 

 

 

     이를 이용한 구간합을 구하는 방법은 이렇다.

 

     글자만으로는 도저히 설명이 어려워 강의 그림을 캡쳐했다.

     이를 그래프로 도식화 하면 이렇다.

 

   

 : 좀 더 자세한 설명..
     실제로 구현해보려 했을때, 사실 이 강의만 보고 나는 도저히 이해를 할 수 없었다.
     아주 손쉽게 구간합을 구할 수 있는 메커니즘임은 자명해 보였으나
     정확히는 ' 특정 값을 변경할 때 0이 아닌 마지막 비트만큼 더하면서 ' 
     사설이지만 이게...무슨 말인가? 알고리즘 공부를 하며 하루하루 스스로가 빠가사리라는 생각을 해왔지만
     이건 너무하다는 생각이 들었다. 내가 2진법을 몰라서 못 알아듣는건가 싶기도하고

     각설하고 다른 설명글들을 찾아보았다.
     부디 나처럼 이게 이해가 안가는 분들에게 도움이 되길 바란다.

 

     ( 출처 : https://www.crocus.co.kr/666 )  

 

     우선 구간합을 구하는 부분부터 보자.

 

     이 문장을 좀 더 지칭하는 요소들을 명확한 문장으로 바꾸면 좀 더 이해가 쉽다.

 

     8 + 12 + 14 + 15 인덱스의 값을 더해, 4 인덱스의 값을 빼면

     5 ~ 15 인덱스의 구간합을 구할 수 있다.

     이 때, 연산할 인덱스를 비트값으로 변환해보면 1000 + 1100 + 1110 + 1111 으로 변환할 수 있는데

     더하는 값들을 역순서로 보면 1111 -> 1110 -> 1100 -> 1000 순으로 바뀌는 것을 확인 할 수 있다.

 

     이는 1이 있는 가장 오른쪽 ( 최하위 비트 ) 가 0으로 바뀌는 것이다.

 

     혹시 나처럼 일반적으로 그렇게 되는지 증명이 안되면 사용하기 두려운 분, 

     또 이를 통해 무작정 1을 0으로만 바꾸면 끝인가?

     어디까지 더해야 하는가? 하는 질문이 남는다면

     이 부분까지 생각해보자 혹시 틀린 내용이라면 누군가 지적해주면 언제나 감사하다.

 

     BIT는 인덱스를 다루기 쉽게 1부터 시작한다. 그리고 O( log n )의 시간복잡도를 위해

     리프노드까지 절반으로 나누어 가며 구성한다.

     그리고 짝수 인덱스는 항상 구간합을 가지게된다.

     그래서 홀수값을 포함하면 항상 마지막 비트는 1이 되고,

     그 1을 0으로 바꾸면 바로 아래 구간합을 가진 인덱스를 가리키게 된다.

 

     또한 전체 길이의 중간의 인덱스는 앞의 절반까지의 구간합을 가지고 있으므로,

     중간 이후의 구간합은 절반지점 까지의 인덱스의 구간합들을 더하게되고,

     중간 이전의 구간합은 시작지점 까지의 인덱스의 구간합들을 더하게된다.

     ( 이 내용은 불필요했다. )

 

     이제 조금 명징하게 BIT의 구간합을 도출하는 알고리즘을 구현해볼 수 있을 것 같다.

 

 : 다음으로 Update를 살펴보자

 

     1이 있는 가장 오른쪽 최하위 비트에 1을 더해가면 Update가 필요한 인덱스를 찾아낼 수 있다.

 

     1 ( 1 ) -> 2( 10 ) -> 4 ( 100 ) -> 8 ( 1000 ) -> 16 ( 10000 )

     이처럼 1의 위치에 1을 더하는 것이고

     도식화된 것을 보면 직관적으로 그려지지만..

     이러한 1을 0으로 바꾸는 방향의 증명의 방법은 떠오르지 않는다.

     혹시라도 증명에 관련한 자료가 있나 찾아보았지만 보이지 않는다.

     

     다만 다른 방법으로 깊이와 레벨을 생각해 볼 수 있겠다.

     항상 절반으로 나누는 방식이기에,

     2^(깊이 - 레벨)을 더하면 Update가 필요한 인덱스들을 찾아낼 수 있다.

     다른 증명 방법들도 얼마든지 알려주신다면 감사하다.

 

     Update와 IntervalSum 모두에 대한 설명이 충족된 것 같다.