펜윅트리 (Fenwick Tree)

펜윅트리 Fenwick Tree 는 Binary Indexed Tree (BIT) 라고도 한다.

설명하기 위해, 대표적으로 사용되는 그림을 통해 이해해보도록 하자.

아래에 해당하는 배열은, 각 인덱스를 2진수로 나타내었을 때 마지막 1의 위치를 통해 현재배열 이전에 몇개의 배열을 포함할것인가를 파악할 수 있다.

예를 들어, 인덱스가 10인 위치에서 생각해보면, 10을 2진수로 나타내었을 때 1010(2) 즉 마지막 1의 위치가 2번째에 있기 때문에 현재 10의 위치에서 앞으로 1칸 총 2개의 배열을 포함하는 값이 위 그림에 나와있는 하늘색 10에 포함되게 된다.

12 까지의 SUM을 구한다고 한다면, 하늘색으로 칠해진 8과 12를 더하면 12까지의 SUM 을 구할 수 있다.

그렇다면, Segment Tree 와의 차이점은 무엇일까?

펜윅트리는 세그먼트 트리보다 메모리 소모가 적게 들고, 업데이트 연산의 경우는 해당 범위를 모두 업데이트 해주어야 하지만

BIT 연산으로 진행되기에 계산과정이 더 쉽게 느껴질 것이다 (쉽게 느껴진다는 것은 필자의 주관적인 생각)

앞서 말한 2진수의 마지막 1의 위치를 파악하는 방법은,

 해당 숫자 num 과 -num(num의 보수 ~num+1) 를 & 연산하여 계산할 수 있다.

펜윅트리의 경우 query과정에서 O(logn), update에서 O(logn) 이 소요되며,

총 n개의 값에 대해 O(nlogn)이 걸린다는 것을 알 수 있다.

그렇다면 주요 소스에 대해 알아보자.

아래는 UPDATE 와 SUM 을 구하는 핵심소스이다.

<UPDATE>

#include <cstdio>

void update(int num, long long diff) {
	while (num <= 트리의 크기) {
		Tree[num] += diff;
		num += (num & -num);
	}
}

<SUM>

#include <cstdio>

long long sum(int num) {
	long long ans = 0;
	while (num > 0) {
		ans += Tree[num];
		num -= (num & -num);
	}
	return ans;
}