이진 인덱스 트리(Binary Indexed tree, 이하 BIT)는 prefix sum에서 값을 변경할 때 해당 값을 기준으로 이후의 값들을 전부 다시 계산해야 한다는 단점을 해결해 준다.
1. 트리 구성
1.1. 구간의 크기
이러한 BIT에서는 인덱스를 이진수로 보았을 때, 가장 작은 자릿수를 가지는 1의 위치에 따라 구간의 크기를 정한다. 예를 들어, BIT가 저장된 배열 T에서 12번 노드는 이진수로 1100이다. 이때 1100에서 가장 작은 자릿수를 가지는 1은 4의 자리에 있다. 따라서 12번 노드의 구간은 12-4+1 ~ 12이다. (구간의 크기가 4)
1.2. 가장 작은 1의 위치
위에서 구간의 크기를 정하기 위해 가장 작은 자릿수를 가지는 1의 위치를 사용했다. 이는 다음과 같이 보수와의 bitwise AND를 통해 구할 수 있다.
이런 과정을 거치면 1이 몇 번째에 있든 상수 시간 내에 찾을 수 있다.
2. 구간 합
2.1. prefix sum 구하기
따라서 는 와 구간이 겹치지 않는다. 이를 통해 아래와 같이 를 구할 수 있다.
2.2. 구간 합 구하기
위와 같이 BIT를 통해 prefix sum을 구한 뒤 이를 통해 원하는 구간 합 를 구한다.
3. 업데이트
3.1. 부모 노드 찾기
BIT에서 는 구간 를 가진다. 이를 통해 부모 노드를 찾아보자.
위 그림을 보면, 노드 k의 부모가 k+d이다. 구간 k, k+d가 아래와 같다고 하자.
이때 이므로 구간 는 구간 를 포함한다. 이렇게 가 항상 가 가지는 구간을 포함하기 때문에 노드 의 부모는 노드 이다.
3.2 값 변경
어떤 노드의 값을 변경하면 BIT에서는 해당 노드를 포함하는 구간만 업데이트하면 된다. 위 과정을 통해 부모 노드의 인덱스가 배열의 길이를 벗어날 때까지 부모 노드에 의 값이 변한 만큼 더해주면 된다.
4. 코드
Transclude of Binary_Indexed_Tree.py