[6기 강남 조유석] Binary Indexed Tree

안녕하세요. 강남멤버십 23-1기 조유석입니다.

이번 포스팅에서는 빠르고 간단하게 구간 합을 구하는데 사용되는 Binary Indexed Tree 에 대해 알아보겠습니다.

Segment Tree

Binary Indexed Tree 를 보기 전 먼저 Segment Tree 에 대해 간단히 살펴보겠습니다.

세그먼트 트리는 특정 구간에 대한 질문을 빠르게 답하는 데 사용합니다. 아래와 같은 특징을 가지며, 아래 그림과 같은 데이터 구조를 가집니다.

- 완전 이진트리

- 각 노드는 자신이 가지고 있는 구간에 대한 정보를 가짐

- 각 노드의 자식 노드는 부모 노드의 구간을 이등분한 두 개의 구간 중 한쪽 구간에 대한 정보를 가짐

- 구간에 대한 조작을 O(log n)로 실행

세그먼트 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진트리를 만드는 것이며, 이러한 전처리 과정을 수행해 두면 어떤 구간 [i,j]가 주어지더라도 이 구간을 세그먼트 트리의 노드에 포함된 구간들의 합집합으로 표현할 수 있습니다.

예를 들어, [2,8] 구간은 그림에 진하게 칠해진 세 구간 [2], [3,4], [5,8] 의 합집합으로 표현할 수 있습니다.

Binary Indexed Tree(or Fenwik Tree)

세그먼트 트리의 가장 흔한 사용 예는 구간 합을 빠르게 구하는 것이고, 이 경우 세그먼트 트리 대신 쓸 수 있는 구간 트리의 궁극적인 진화 형태로 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(Binary Indexed Tree)라고 불립니다.

s부터 t까지의 합을 구하고자 할 때, 세그먼트 트리를 사용하면 직접적으로 구할 수 있습니다. 하지만 합의 경우에는 (1부터 t까지의 합) - (1부터 s-1까지의 합)을 계산한다면, s부터 t까지의 합이 됩니다. 따라서, 임의의 i에 대해서는 1부터 i까지의 합을 계산할 수 있다면 충분하다는 것을 알 수 있습니다. 이와 같은 조건을 제한한다면 세그먼트 트리의 오른쪽 방향으로 분기되어 있는 노드의 값이 필요 없어집니다. 이러한 방법을 기반으로 한 자료 구조가 Binary Indexed Tree 이며 세그먼트 트리보다 구현이 쉽고, 고속으로 동작합니다.

- 뒷자리가 1로 끝나는 1, 3, 5, 7은 길이가 1

- 뒷자리가 1개의 0인 2, 6은 길이가 2

- 뒷자리가 2개의 0인 4는 길이가 4

- …

Binary Indexed Tree에서는 이러한 특성을 이용해 각각의 조작을 간단한 비트연산으로 작성할 수 있습니다.

먼저, Binary Indexed Tree에서 n번째 원소까지의 부분합을 구하는 과정을 살펴보겠습니다.

예를 들어, 7까지의 합을 구하하기 위해 4, 6, 7 번째 원소의 합을 구해야 하며 그 과정을 보면 다음과 같습니다.

각 과정에서 맨 오른쪽에 있는 1 비트를 빼줌으로서 다음 과정으로 진행됩니다.

다음으로 Binary Indexed Tree에서 n번째 원소에 값을 더하거나 빼는 경우를 살펴보겠습니다.

예를 들어, 5번째 원소의 값을 더하거나 뺄 경우 변경해야 할 원소는 5, 6, 8 이며 그 과정을 이진수로 표현하면 다음과 같습니다.

부분합을 구할 때와는 반대로 맨 오른쪽에 있는 1 비트를 더해줌으로서 다음 과정으로 진행됩니다.

컴퓨터가 음수를 표현하기 위해 2의 보수를 사용한다는 점을 이용하여 맨 오른쪽 1비트를 찾는 것을 (idx & -idx)와 같이 간단하게 구현할 수 있으며 이를 이용해 부분합을 계산하는 sum() 함수, Binary Indexed Tree 를 갱신하는 add()함수를 아래와 같이 구현할 수 있습니다.

이 두 연산에서 반복문이 수행될 때마다 트리의 한 층을 올라가는데, 트리의 높이는 항상 O(log n) 이기 때문에, 이 두연산의 시간복잡도는 모두 O(log n)입니다.

Binary Indexed Tree 의 구현은 엄청나게 간결하기 때문에, 계속 변하는 배열의 구간 합을 구할 때는, 세그먼트 트리보다 자주 사용하게 됩니다. 

최근에는 ACM-ICPC Asia Regional Daejeon Site 2013 에서 Binary Indexed Tree 를 이용해 푸는 문제가 출제되었습니다.(Problem I: Permutation Graphs)

http://acm.kaist.ac.kr/2013/MainContest/problemset.pdf

공부하고 풀어보는 것도 좋을 것 같습니다.

이상으로 Binary Indexed Tree 에 대해 알아보았습니다.

앞으로 문제해결을 위한 자료구조, 알고리즘 몇 가지를 더 알아보겠습니다.

감사합니다.

Reference

  - ‘프로그래밍 대회에서 배우는 알고리즘 문제해결 전략’ - 구종만 저

  - ‘프로그래밍 콘테스트 챌린징’ - Takuya Akiba, Yoichi Iwata, Masatoshi Kitagawa 저