Binary Indexed Tree(또는 fenwick tree, 이하 BIT)는 Segment Tree와 비슷하게 구간에 대한 정보를 저장할 수 있는 자료구조입니다. 기본적으로 아래의 그림과 같은 1-based 구조를 가지며, 구간합 등을 알아내는데 사용됩니다.
BIT는 위의 그림처럼 세그먼트트리보다 조금 더 단순화된 구조를 가지지만, 구간에 대한 정보를 [1,X]으로 알아낼 수 있다는 점이 다릅니다.
위 그림의 2번지에 그려진 1번지~2번지의 박스는 [1,2]의 구간의 정보를 [2,2]에 가지고 있다는 것을 의미합니다. 마찬가지로 12번지는 [9,12]의 구간의 정보를 가지고 있는 것입니다. 이를 적절히 이용하여 원하는 구간의 정보들을 구하는 것입니다.
BIT로 구간의 합을 알아보겠습니다.
트리의 구성은 먼저 최대 구간으로 배열을 잡습니다. 1-based 트리구조이므로 유의하여 배열을 선언합니다. 트리에 자료를 삽입할 때는, 트리의 원하는 번지 X에 원하는 값 Y를 누적하여줍니다. 그리고 X를 X+LSB(X)로 옮겨, 옮겨진 위치에도 Y를 누적시켜줍니다. 이 방법을 X가 배열의 범위를 벗어나지 않을 때까지 반복합니다. (*LSB=최하위비트)
이렇게 완성된 트리에서 [1, X] 구간의 합을 알아내는 과정은 다음과 같습니다. 먼저 X를 11이라고 할 때, 직관적으로 우리는 트리의 8번지와 10번지와 11번지를 모두 더하면 1~11번지의 합을 구할 수 있음을 알 수 있습니다.
이 또한 LSB를 이용하여 해결할 수 있습니다.
X = 1일 때, 11 - LSB(11) = 10이 됩니다. 또 10 - LSB(10) = 8, 8 - LSB(8) = 0입니다.
결국 [1,X]의 누적합을 알기 위해선, X의 트리 값을 더한 후 X를 X-LSB(X)로 옮겨가면서 X가 0이 될 때까지 반복하면 누적합을 얻을 수 있습니다.
BIT는 세그먼트 트리에 비해 간단한 구현과 적은 메모리로 구현이 가능하지만, 세그먼트 트리는 다양한 목적으로 사용이 가능하므로 필요에 따라 사용해야 합니다.
다음은 누적된 값을 알아내는 BIT 코드입니다.
| 입력 | 출력 |
| 첫 번째 줄에 배열 D의 원소의 수 N, 두 번째 줄에 D의 원소들이 주어지며 세 번째 줄에 정수 M이 주어진다. 네 번째 줄 부터 M + 3 번째 줄 까지 정수 Xi가 주어진다. |
각각의 정수 Xi에 대해 D[1, Xi]의 합을 출력한다. |
| 7 1 -5 6 7 2 3 10 3 5 1 7 |
11 1 24 |
import java.util.ArrayList;
import java.util.Scanner;
class BIT {
ArrayList<Integer> T;
int S;
public BIT(int n) {
this.S = n;
T = new ArrayList<Integer>();
for (int i = 0; i <= n; i++) T.add(0);
}
void Update(int p, int v) {
while (p <= S) {
T.set(p, T.get(p) + v);
p += p & (-p);
}
}
int Sum(int p) {
int ret = 0;
while (p > 0) {
ret += T.get(p);
p -= p & (-p);
}
return ret;
}
}
public class Main {
int v[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
BIT bit = new BIT(n);
for (int i = 1; i <= n; i++) {
int x = sc.nextInt();
bit.Update(i, x);
}
int m = sc.nextInt();
for (int i = 0; i < m; i++) {
int x = sc.nextInt();
System.out.println(bit.Sum(x));
}
}
}