Fenwick Tree (Binary Indexed Tree, BIT)

Fenwick Tree (a.k.a. Binary Indexed Tree, BIT)에 대해 알아보도록 하겠다.

펜윅의 기능은 segment tree와 비슷하고, 더 한정적이다. 하지만 비재귀로 쉽게 구현이 가능하고 속도가 훨씬 빠르다. (세그로 짠 $O(logN)$보다 펜윅으로 짠 $O(log^2N)$이 더 빠를 정도.) 그렇기 때문에 펜윅으로 구현이 가능하다면 세그 대신 펜윅을 사용하는 것이 좋다.

 

수열의 누적합 문제를 풀어보자. 수열 $A[1 ... N]$에 대해 $A[i]$의 값을 바꾸는 점 갱신 쿼리와, 누적합 $A[1] + ... + A[i]$를 구하는 쿼리가 들어온다. 편의상 $N=2^m$이라 하자. 펜윅 $bit[1 ... N]$은 $A$의 구간합에 해당하는 값을 가진다. 구체적으로는, $bit[i]=A[i - k + 1] + A[i - k + 2] + ... + A[i]$이다. $k$는 $i$의 약수인 2의 거듭제곱 중 가장 큰 수이다. 이는 $i$를 이진수로 표현했을 때 일의 자리 쪽에 0이 몇 개나 연달아 나오는지와 관련이 있다. $i=2^m=100...0_{(2)}$일 때는 $k=2^m$이고, $i=2^{m-1}=010...0_{(2)}$또는 $i=2^m+2^{m-1}=110...0_{(2)}$일 때는 $k=2^{m-1}$이다.

점갱신이 이루어질 때는 최대 $m$개의 값만 갱신해주면 되고, 누적합을 알고 싶을 때는 최대 $m$개의 합을 구하면 된다. 시간복잡도는 $O(logN)$이다. 자세한 내용은 코드 참고. 코드에서 $rb(x)$란 right most bit로, 앞에서 설명한 $k$이다.

세그멘트 트리에서는 임의의 연속된 구간에 대한 값을 구할 수 있었던 것에 비해, 펜윅에서는 $i=1$에서 시작되는 구간에 대한 값만 알 수 있다(ex. 구간합 대신 누적합). 구간합의 경우에는 누적합의 차로 구할 수 있어 문제가 되지 않지만, RMQ와 같은 경우에는 이것이 제약이 된다.

 

펜윅으로 할 수 있는 또 다른 기능에는 lower_bound가 있다. $A$의 값들이 모두 양수일 때, $A$의 누적합 $S$는 증가수열이 된다. $S$에 대한 lower_bound 연산 역시 $O(logN)$으로 할 수 있다. 

 

이제 2d 펜윅에 대해 알아보자. 개념은 2d 세그와 마찬가지이다. $bit\_2d[1...N][1...N]$에 대해, $bit\_2d[i]$는 $A[i - k + 1 ... i][1...N]$에 대한 1차원 펜윅이다. 이중 for문을 이용하면 간단하게 구현할 수 있고, 점갱신과 구간(1차원일 때와 마찬가지로 (1, 1)을 포함하는 구간) 쿼리는 $O(log^2N)$이다.

 

아래는 펜윅 코드이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

#define rb(x) ((x)&(-(x)))

const int LOGN = 18;
const int MAXN = 1 << LOGN;

lint bit[MAXN];
lint bit_2d[MAXN][MAXN];

void updbit(int x, lint z) {			// A[x] += z
	for(int i = x; i < MAXN; i += rb(i)) bit[i] += z;
}

lint gbit(int x) {				// A[1] + ... + A[x]
	lint ans = 0;
	for(int i = x; i; i -= rb(i)) ans += bit[i];
	return ans;
}

int lbbit(lint z) {				// lower_bound
	int pos = 0;
	for(int i = LOGN - 1; i >= 0; i--) {
		if(pos + (1 << i) < MAXN && bit[pos + (1 << i)] < z) {
			z -= bit[pos + (1 << i)];
			pos += (1 << i);
		}
	}
	return pos + 1;
}

void updbit2d(int x, int y, lint z) {		// A[x][y] += z
	for(int i = x; i < MAXN; i += rb(i))
		for(int j = y; j < MAXN; j += rb(j))
			bit_2d[i][j] += z;
}

lint gbit2d(int x, int y) {			// sum(A[1...x][1...y])
	lint ans = 0;
	for(int i = x; i; i -= rb(i))
		for(int j = y; j; j -= rb(j))
			ans += bit_2d[i][j];
	return ans;
}