펜윅 트리(Fenwick Tree, BIT)

[펜윅 트리]

펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(BIT, Binary Indexed Tree)라고도 불린다.

펜윅 트리는 구간 트리에서 부분합에 대한 질의를 더 효율적으로 하기 위해 만들어졌다. 부분합을 통해 구간합을 구할 수도 있으므로 구간합에 대한 질의도 답할 수 있다.

 

단순히 부분합만 구한다고 하면 당연히 트리구조를 사용할 이유가 없지만, 원소를 변경할 때는 트리구조의 장점이 들어난다. 배열로만 부분합을 구현했다면, 배열의 원소가 바뀔때마다 O(N)의 연산을 해줘야한다. 하지만 펜윅트리는 이를 O(logN)만큼만 걸리게 함으로써 속도를 올린다. 

 

펜윅 트리는 기존 구간트리에서 각 노드에 대해 right에 해당하는 자식 노드들을 죄다 지운 형태다. 이유는 부분합 자체가 배열의 첫 i개의 원소들의 합(0~i번 인덱스까지의 합)이기 때문에 굳이 right에 해당하는 구간을 넣지 않아도 충분히 부분합을 계산할 수 있기 때문이다.

 

이름에 이진 인덱스라는 것이 붙은 이유는 각 구간에 대한 인덱스를 이진수 표현으로 만들어서 모든 연산을 처리하기 때문이다. 다만 인덱스를 1부터 시작해야한다는 부분이 헷갈릴 수 있다. 이유는 차차 알아가보자.

 

1~5까지 각 숫자들을 이진수로 나타내보자.

1 = 001₂
2 = 010₂
3 = 011₂
4 = 100₂
5 = 101₂

빨간색으로 표시된 부분은 가장 오른쪽에있는 1을 표시한 것이다. 이는 구간을 나타낸다.

1같은 경우 구간의 길이가 1, 2같은 경우 구간의 길이가 2, 3같은 경우에는 구간의 길이가 1이다.

구간을 시각화 했을 경우

위 구간을 보면 1~2까지는 그냥 인덱스 자체로 1부터 인덱스까지의 부분합을 나타낼 수 있지만, 1부터 3까지의 부분합은 3에 해당하는 구간과 2에 해당하는 구간을 더해야한다. 

 

이제 구현해보자.

구간이 저장될 vector(tree)를 만들고, 크기는 N+1로 만들어 1부터 인덱스가 시작하도록 하자.

1. 부분합 구하기(sum)

부분합을 어떻게 구할 수 있을까?

잘... 살펴보면 3의 인덱스의 이진수 표현에서 011₂에 해당하는 구간과 010₂에 해당하는 구간을 더하면 부분합이 된다는 것을 알 수 있다. 즉, 맨 오른쪽부터 1을 하나씩 지워 나가면서 더하면 부분합을 구할 수 있다는 것이다. 예를 들어, 5같은 경우엔 101₂에 해당하는 구간을 더한 후 101₂에서 맨 오른쪽에 해당하는 1을 지운 100₂을 더하고 다시 100₂에서 맨 오른쪽에 있는 1을 지우면 000₂이 되므로 더이상 더할 구간이 없다.

 

이를 구현하기 위해서는 비트마스크에 대해 알아야한다. 자세한 개요와 테크닉은 다른 포스팅에 다루도록 하겠다.

 

맨 오른쪽에 있는 1을 찾아 원래 값에서 빼기 위해서는 두가지 방법이 존재한다.

• 어떤 수 x와 x-1의 비트들을 AND연산
• 어떤 수 x와 -x의 비트들을 AND연산한 값을 x에서 빼기.

예를 들어 어떤 수 x가 6이라고 하면 이진수 표현은 110₂이다.

 

이를 첫번째 방법으로 x에서 맨 오른쪽에 있는 1을 지워보자.

6에서 1을 뺀 5의 이진수 표현은 101₂이 된다. 이제 둘을 AND연산하게 되면 어떤 수의 맨 오른쪽 1을 지울 수 있게된다.

 

두번째 방법은 2의 보수라는 개념을 알아야한다.

2의 보수란 컴퓨터에서 음수를 저장하기 위해 사용하는 방법으로 어떤 수 x에 대해 NOT연산을 해준 후 1을 더하면 된다(~x + 1). 즉, 위 예시에서 6의 보수표현은 010₂이다. 6과 -6을 AND연산하고 이를 6에서 빼게되면 맨 오른쪽 1을 지울 수 있게된다.

 

코드로 표현하면 다음과 같다.

int sum(int pos) {
	++pos;
	
	int ret = 0;
	while(pos > 0) {
		ret += tree[pos];
		pos -= (pos & -pos);
		// 또는 pos &= (pos-1);
	}
	
	return ret;
}

 

외부에서 인덱스를 따질때는 0부터 세기때문에 함수 내부에서는 1을 증가시켜 계산시켰다.

 

2. 수 변경하기(update)

펜윅 트리는 구간 트리처럼 모든 구간에 대해 답을 계산하지 않기 때문에 O(N)에 초기화하기가 불가능하다. 따라서 구간 트리의 갱신 연산처럼 각 위치의 값을 변경하는 연산을 통해 내용을 채워넣어야한다.

 

구간 트리처럼 한 위치의 값을 변경하면 그 위치랑 관련된 구간은 모두 변경 전과 후의 차이(diff)만큼 더해주면 된다. 어떤 위치와 관련된 모든 구간들은 해당 위치부터 끝까지 맨 오른쪽에 있는 1만큼 계속 더해주면서 구간에 diff만큼 더해주면 된다.

 

맨 오른쪽에 있는 1을 구하는 방법은 원래 수 x와 x의 보수를 AND연산하면 되기 때문에 시작 위치부터 계속 계산해서 더해주면 된다.

 

코드로 구현하면 다음과 같다.

void update(int pos, int diff) {
	++pos;
	int s = tree.size();
	while(pos < s) {
		tree[pos] += diff;
		pos += (pos & -pos);
	}
}

 

위 두 연산의 시간 복잡도는 모두 O(logN)이다. 많이 돌아봐야 트리의 높이만큼 돌 수밖에 없기 때문이다.