Fenwick Tree

Segment Tree보다 범용성은 낮지만 훨씬 가볍고 실행 속도도 조금 더 빠른 Binary Indexed Tree(Fenwick Tree)에 대해 설명하겠습니다.

Fenwick Tree는 Segment Tree처럼 구간의 정보를 log(n)으로 찾고, update하는 자료구조입니다. 하지만 세그먼트 트리가 모든 구간 [l,r]에 대하여 find, update할 수 있는데 반해 Fenwick Tree는 [1,x] 구간만을 find, update할 수 있습니다.

따라서 Fenwick Tree에서는 구간 [l,r]의 최댓값이나 최솟값 등을 찾기 어렵습니다. (구간의 합, 곱과 같은 정보는 Fenwick에서도 찾을 수 있습니다.)

1. Update

void update(int i, int d){
	while(i<=n){
		bit[i]+=d;
		i+=(i&-i);
	}
}

2. Find

int find(int i){
	int ans=0;
	while(i>0){
		ans+=bit[i];
		i-=(i&-i);
	}
	return ans;
}