[DS] [BIT] Binary Index Tree

이진인덱스트리

흔히 계속 변하는 배열의 부분합을 구할때

FOR i N to M
으로 복잡도 O(n) 으로 구할수도 있겠지만,

이런 자료구조의 궁극적 사용 목표는 빠르게 하기 위해서 이다.

보통 이럴때 세그먼트 트리를 사용하는데,

0부터 N까지의 합 을 구할때는 세그먼트 트리보다 구현이 간단하면서 빠른

이진 인덱스 트리를 사용하게 된다.

(세그먼트 트리는 N부터 M 까지)

1부터 8까지의 배열이 있다고 가정한다면

이진 인덱스 트리는 다음과 같이 생겼다.

이진인덱스 트리는 배열로 구현하며

0번째는 사용하지 않는다.( 이유는 뒤에서 설명한다)

V={} 를 어떠한 배열이라고 하고, 우리는 V의 부분합을 구할 것이다.

이진인덱스트리를 E라고 표기한다.

E[1] 는 V의 첫 원소부터 첫원소까지의 합을 저장한다.

E[2]는 V의 첫원소부터 두번째 원소까지의 합을 저장한다.

E[4] 는 V의 첫원소부터 4번째 원소까지의 합을 저장한다.

예를들어 5까지의 합을 구하려 한다면

1~4 까지의 합 + 5의 합 을 더해주면된다.

그림으로 보면 E[4]+E[5] 가된다.

4 는 2진수로 0100 이고

5는 2진수로 0101 이므로

5를 먼저 결과값에 더하고, 5의 맨 오른쪽에 있는 1의 비트 값만큼 빼면된다.

그 인덱스가 0이 될때까지 반복하면 된다.

4의 맨 오른쪽 1 비트는 100 이고 이를 빼면 0이되므로 본 합 계산을 완료한다.

맨 오른쪽 비트 찾는 공식은 A & -A 연산으로 찾을수 있다.

손으로 해보면 왜 그런지 쉽게 알 수 있다.

값을 추가 하는 공식은 만일 5번째에 값을 추가하게 되면, 그림상

5 , 5~6 , 1~8 이 5를 포함하므로

E[5], E[6], E[8] 에 값이 추가되어야 한다.

이는 합을 구할때와 반대로 맨 오른쪽 비트값만큼 더 해주면된다.

V배열의 크기가 넘지 않을때까지

아래는 값을 추가할때 와 합을 구하는 코드이다.

#define NSIZE 100
int tree[NSIZE];  
void AddBIT(int idx, int val){  
 while (idx <= NSIZE){
  tree[idx] += val;
  idx += (idx&-idx);
 }
}
void SumBIT(int idx){  
 int ret = 0;
 while (idx){
  ret += tree[idx];
  idx -= (idx&-idx);
 }
 return ret;
}

두 함수의 복잡도는 모두 O(logn) 이다.