펜윅트리 / 바이너리인덱스트리 (Binary Indexed Tree) 에 대하여

 Binary Indexed Tree(이하 BIT) 는 알고리즘이라기 보다는 자료구조에 가깝지만, 흔히 기본 자료 구조라고 할 수 있는 스택, 큐와 같은 자료구조보다는 고급의 자료구조이다. 사촌 격인 Segment Tree 도 있으나 조금 더 설명하기가 어렵기 때문에 본 포스팅에서는 Binary Indexed Tree 만 소개한다.

BIT의 원래 명칭은 Fenwick Tree 이며, 구현 상 Binary Tree 를 이용하기 때문에 BIT(Binary Indexed Tree) 라고 부른다. 

이 이진트리 형태의 자료구조는 효과적으로 부분 요소의 갱신(Update) 와 조회(Select) 를 하기 위하여 만들어진 자료구조로, 많은 변경과 많은 데이터의 조회가 빈번하게 일어날 때 한번에 처리할 수 있는 간단하면서도 유용한 자료구조이다.

특히, 데이터의 일부분이 갱신되었을 때 데이터 전체의 값이 변하는 경우, 가령 데이터 전체의 총합을 구하거나 최댓값을 구하는 일 등을 가장 효과적으로 수행할 수 있는 자료구조이다.

설명을 위해 다음 배열을 준비해보았다.

준비한 배열은 음... 온라인 게임의 유저들의 점수를 나타낸 랭킹 Database라고 해보자. 6명의 유저들이지만 엎치락 뒤치락하고 있는 것을 볼 수 있다. 

이 데이터베이스에서 가장 점수가 높은 유저는 맨 앞에 있는 10점을 획득한 유저이고, 최고점은 10점이다. 최고점을 우리는 DB를 모두 뒤져 시간복잡도 O(N) 만에 최댓값을 찾아내었다. 그런데 10분뒤 상황이 바뀌었다.

갑자기 몇몇 유저의 약진에 힘입어 10점을 획득한 유저는 3등이 되었다. 이런.. 당신은 다시 최고점을 구하기 위하여 DB를 모두 뒤져 최댓값 15를 찾아내기에 이른다. 시간복잡도는 O(N)

이 구조는 효과적일까? 전혀 그렇지 않다. 심지어 실시간 게임이라면 이런식으로 관리했다간 100만명의 유저에 대해 매 Tick 마다 100만명을 전부 검사해야 한다. 물론 알고리즘의 적용 대상을 이런 종류의 실시간 서비스를 예시로 드는건 적절하지 않아보이지만, 더 최적화할 수 있는 방안은 분명히 있다.

<BIT 가 적용된 새로운 자료구조>

위의 그림은 BIT 가 적용된 새로운 자료구조를 보여준다. 위에 보이는 것 처럼 Binary Tree 를 이용한 구조는 추가적인 메모리를 사용하지만, 토너먼트 형태로 최댓값을 구해내고 있다. 또한 보면 알 수 있겠지만 범위별로 최댓값을 구하는 것도 가능하다. 토너먼트를 해당 범위에 대해서만 열면 그만이다.

 눈치챌 수 있겠지만 이 자료구조는 토너먼트 형식을 이용해서 비교해야할 대상과만 비교한다. 가령, A가 B보다 크다는게 보장이 되었을 때, C가 B보다 크다면 A와 C는 서로 비교할 필요가 없다. 전부 비교할 필요 없이 두번만에 최댓값 C를 구할 수 있는 것이다.

다음 코드는 이를 좀 더 명확히 나타내며 C로 작성된 코드지만 이해하기 어렵지 않을 것이다.

#define max(a,b) ((a)>(b)) ? (a):(b)

const int BMAX = 100000;

int bit[2*BMAX+1] = {0, };

void set(int a, int v)

{

a+=BMAX, bit[a] = v;

while(a/=2)

bit[a] = max(bit[2*a], bit[2*a+1]);

}

int get(int l, int r)

{

l+=BMAX, r+=BMAX;

int ans = 0;

while(l<=r)

{

if(l%2==1)

ans = max(ans, bit[l]), l++;

if(r%2==0)

ans = max(ans, bit[r]), r--;

l/=2, r/=2;

}

return ans;

}

 코드를 보면 추가적인 공간을 할당해, 그부분 부터 값을 채우면서 루트 노드에 최댓값을 갱신하고 있는 모습이다.

위의 코드를 이용하면 set 을 통해 인덱스 a에 값 v를 저장하여 펜윅트리를 구성할 수 있고, get 함수를 통해 l 부터 r 까지 범위 내에 있는 최댓값을 어렵지 않게 구해낼 수 있다.

물론 시간복잡도는 set 하는 부분에서 O(logN) 이 소모되지만 get 하는 부분에서 O(logN) 의 효율성을 보인다.

기존에 최댓값을 구하려면 범위 내 모든 요소를 검사해야 했던 O(N) 의 자료구조보다 향상된 범위 검색(Select) 퍼포먼스를 낼 수 있는 것이다. 물론 이를 위해 값의 갱신(Update) 에 O(1) 이 아닌 O(logN) 의 비용을 지불하지만 이는 어떤 종류의 데이터들에 대해 훨씬 효율적일 수 있다.

이번에 포스팅 한 BIT의 경우 Single Update (포인트 갱신) & Range Query (범위 검색) 이지만, 이를 좀 더 수학적으로 개선하면 Range Update (범위 갱신) & Range Query (범위 조회) 에 있어서도 구현이 가능한 막강한 자료구조를 만들어 낼 수도 있다. 이는 Segment Tree 포스팅 이후에 별도로 포스팅을 할 예정이다. (내용이 어렵다 ㅜ)