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

1. 개념 정리

1) 이진 인덱스 구조를 활용하여 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조

2) 펜윅 트리(Fenwick Tree)라고도 불린다.

3) 세그먼트 트리보다 구현하기 편하고 속도가 빠르다.

  - 세그먼트 트리는 필요한 리프 노드만 채우기 때문에 불완전 트리지만, 인덱스 트리는 리프 노드를 모두 채워서 만들기 때문에 인덱스를 활용할 수 있다.

  - 데이터의 개수가 N개일 때, 세그먼트 트리를 만들기 위해 필요한 공간을 통상 4*N만큼 준비했었다면 인덱스 트리를 만들 때는 N만큼만 준비하면 된다.

4) 인덱스는 1부터 사용하고, 인덱스를 활용하면 해당 인덱스의 값이 몇 개의 데이터의 합인지 알 수 있다.

  - 8비트로만 간단히 예시를 들어보면, 3과 -3을 비트 and 연산을 해보면 다음과 같다.

 3 ==                 0000 0101
-3 == 1111 1010 + 1 = 1111 1011 // 2의보수
-> 3 & -3 ==          0000 0001 == 1
-> 인덱스 3에는 데이터 1개의 합이 저장되어 있다.

  - 인덱스가 1부터 16까지 있다고 하면, 각 인덱스 별로 비트 연산 결과와 의미는 다음과 같다.

5) 값 변경이 일어났을 경우 세그먼트 트리와 인덱스 트리 모두 시간 복잡도는 O(lgn)이다.

- 세그먼트 트리는 루트 노드부터(top-down approach), 인덱스 트리는 리프 노드부터(bottom-up approach) 값 변경이 일어난다.

 

2. 예시

1) 값 변경

  - 3번째 데이터의 값이 변경 됐다면, 인덱스 트리는 인덱스 3부터 값 변경이 일어난다.

  - 이후 순서는 인덱스의 비트 연산 결과를 더하면서 이동하면 된다.

   인덱스 3의 값 변경 -> 3의 비트 연산 결과는 1
-> 인덱스 (3+1=)4의 값 변경 -> 4의 비트 연산 결과는 4
-> 인덱스 (4+4=)8의 값 변경 -> 8의 비트 연산 결과는 8
-> 인덱스 (8+8=)16의 값 변경 -> 16의 비트 연산 결과는 16 -> 종료

2) 첫 번째 데이터부터 x번째 데이터까지의 합 구하기

  - 첫 번째 데이터부터 11번째 데이터까지의 합을 구한다고 하면, 인덱스 11부터 더한다.

  - 이후 순서는 인덱스의 비트 연산 결과를 빼면서 이동하면 된다.

   인덱스 11의 값 더하기 -> 11의 비트 연산 결과는 1
-> 인덱스 (11-1=)10의 값 더하기 -> 10의 비트 연산 결과는 2
-> 인덱스 (10-2=)8의 값 더하기 -> 8의 비트 연산 결과는 8 -> 종료

3) a번째 데이터부터 b번째 데이터까지의 합 구하기

  - 2)번을 활용해서 (b번째 데이터까지의 합) - (a-1번째 데이터까지의 합)으로 구할 수 있다.

 

3. 구현 코드

// 1) 메서드 구현

// i번째 데이터의 값 변경이 일어났을 때
// dif: i번째 데이터의 (변경 후 - 변경 전)의 값. 커졌다면 dif>0
static void update(int i, int dif) {
    while(i<=number) {
        tree[i] += dif;
        i += (i&-i); // i의 비트 연산 결과만큼 더하면서 이동
    }
}

// 1부터 n까지의 합
static int sum(int n) {
    int ans = 0;
    while(n>0) {
        ans += tree[n];
        n -= (n&-n); // n의 비트 연산 결과만큼 빼면서 이동
    }
    return ans;
}
	
// a번째부터 b번째까지의 합
static int getPart(int a, int b) {
    return sum(b) - sum(a-1);
}

// 2) 메서드 사용

// 클래스 변수
static int number = 16; // 16개의 데이터
static int[] tree = new int[number+1]; // 이진 인덱스 트리

// main()
int[] data = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}; // 0은 사용하지 않음
for(int i=1 ; i<=number ; i++) // 값 변경 메서드를 호출해
    update(i, i);              // 모든 데이터의 구간 합 저장
System.out.printf("1부터 10까지의 합 = %d\n", sum(10));
System.out.printf("10부터 14까지의 합 = %d\n", getPart(10,14));
System.out.println("    첫 번째 데이터의 값을 1에서 0으로 바꾼다.");
int newValue = 0;
int dif = newValue - data[1];
data[1] = newValue; // 계속 변경이 될 수 있으므로 데이터 배열도 업데이트
update(1,dif);
System.out.printf("1부터 10까지의 합 = %d\n", sum(10));
System.out.printf("10부터 14까지의 합 = %d\n", getPart(10,14));
// print문 출력 결과
1부터 10까지의 합 = 55
10부터 14까지의 합 = 60
    첫 번째 데이터의 값을 1에서 0으로 바꾼다.
1부터 10까지의 합 = 54  // 첫 번째 데이터의 값 변경에 영향을 받는다.
10부터 14까지의 합 = 60 // 첫 번째 데이터의 값 변경에 영향을 받지 않는다.