펜윅트리

펜윅트리는 이진트리기반의 자료구조이며, 세그먼트 트리의 원리를 가지고 있습니다.

 

세그먼트 트리?

여러 개의 데이터가 존재할 때 특정 구간의 합 혹은 최소값, 최대값 등을 구하는데 사용하는 이진 트리 형태의 자료구조입니다. 저는 이것을 어떻게 써야할지 단번에 이해가지 않아서 BOJ BOOK의 설명에 따라 그림과 함께 이해하였습니다. 만약, 이러한 문제가 있다고 합시다.

크기가 n인 정수 배열 a가 있으며, 다음 연산을 최대 m번 수행합니다.
	1. 구간 l, r이 주어졌을 때, a[l] + ... + a[r] 합 출력하기
	2. i번째 수를 v로 바꾸기

int[] a = {4, 6, 2, 1, 7, 5, 8};

 

주어진 a 배열은 위와 같습니다. 일단 문제에서 구간 l, r이 주어졌을 때의 구간합을 구한다라고 하면 보통 단순하게 l부터 r까지 배열의 원소를 하나하나 탐색하며 더하는 방법을 생각할 수 있습니다. 이러한 방법은 구간이 0부터 a.length까지 주어진다면 총 시간 복잡도가 O(n) 이 됩니다.

int sum = 0;
for (int i = l; i <= r; i++)
sum += a[i];

 

2번째 연산의 경우는 배열을 사용하기 때문에 O(1)의 시간 복잡도로 원소 수정이 가능합니다. 이러한 연산을 총 M번 수행하니까 실제 해당 로직의 시간 복잡도는 O(NM)이 됩니다.

 

누적합을 이용한다면 어떨까요? 누적합은 1번 연산을 O(1)로 줄일 수 있습니다. 하지만, 원소 수정이 일어나면 해당 구간까지의 구간합을 다시 연산해야 하므로 2번 연산의 경우는 O(N) 이 됩니다. 그러면 위와 동일하게 O(NM)이 됩니다. 누적합이라는 알고리즘 기법을 사용했음에도 실제 시간 복잡도는 전혀 줄어들지 않은 것입니다. 이때 사용할 수 있는 것이 바로 '세그먼트 트리'입니다.

 

세그먼트 트리는 이진 트리의 각 노드에 구간합의 값을 저장해둡니다.

 

최상단 노드에서는 인덱스 [0-6]까지의 합, 자식 노드부터는 [0-3], [4-6] 까지의 합. 이런식으로 주어진 데이터의 범위를 반으로 분할해가며 구간들의 합을 저장해놓는 것입니다. 그러면 리프 노드의 값에는 각각 배열 a의 원소가 들어가며 부모 노드는 왼쪽 자식과 오른쪽 자식을 합해 구간의 합을 구할 수 있게됩니다. 이를 인덱스 구간으로 표현하면 다음과 같습니다.

 

 

위의 문제로 다시 돌아가 1번 연산에서 l과 r이 (3, 6)이라면 트리를 타고가 [3-3] + [4-6]만 해주면 됩니다. 트리를 탐색하는 시간복잡도는 O(logN) 이므로 1번 연산은 O(logN)만에 해결이 가능합니다. 2번 연산도 마찬가지로 O(logN) 입니다. 왜냐면, 3번 인덱스를 수정하는 경우 3번 인덱스를 포함하는 노드에 대해서 원래 구간합 += 수정할 값 - 원래 3번 인덱스 값의 연산만 적용하면 바로 해당 구간합들이 모두 수정되기 때문입니다. 즉, 트리만 탐색하고 배열 값에 대해 더하기 연산만 해주는 것입니다. 그래서 O(logN) 입니다.

 

이러한 특징을 가진 세그먼트 트리를 활용하면, 구간합 뿐만 아니라 해당 구간에서의 최소값, 최대값을 저장해서 어떤 구간에서의 최소값, 최대값도 O(logN)만에 해결이 가능해집니다.

 

이제, 펜윅트리에 대해서 알아보겠습니다.

 

펜윅트리

펜윅트리는 위의 세그먼트 트리에서 한 단계 더 응용된 자료구조입니다.

 

세그먼트 트리는 각 구간별 모든 합을 세그먼트 즉, 노드에 저장해서 관리하지만 펜윅트리는 모든 세그먼트를 만들 필요가 없습니다. 다음과 같이 간단하게 구성해도 모든 경우의 수를 구할 수 있게됩니다

 

 

펜윅트리의 특징은 홀수번 인덱스들은 배열의 값을 그대로 저장하고, 짝수번 인덱스들이 각각 구간합을 저장하고 있다는 점입니다. 또한, 세그먼트 트리처럼 O(logN) 만에 구간합들을 찾을 수 있음에도 메모리 공간을 더 효율적으로 사용할 수 있다는 것이 특징입니다.

 

그럼, 어떤식으로 펜윅트리가 동작하는지 한번 알아보겠습니다. 펜윅트리는 Tree 배열 속 각 원소를 해당 인덱스에서 인덱스의 최하위 비트 범위만큼 구간합으로 정의합니다. 이것이 무슨 말이냐. 이를 위해 아래 3개의 수의 최하위 비트를 보겠습니다.

3 = 11 -> 1
8 = 1000 -> 8
12 = 1100 -> 4

 

펜윅트리는 이 십진수 값을 이용해 자신을 포함한 범위에 해당하는 구간합을 가집니다. 즉, Tree[3]을 [3, 3] 구간의 합으로 정의하며, Tree[8]은 [1, 8], Tree[12]는 [9, 12] 구간의 합으로 정의합니다. Tree[13]이면 어떨까요? 13은 1101이므로 최하위 비트가 1입니다. 그럼 Tree[13]은 [13, 13] 구간의 합을 갖고 있다는 것을 알 수 있습니다.

 

그럼, 제가 만약 여기서 [1, 13] 구간의 합을 구하고 싶다면 어떻게 할 수 있을까요? sum = Tree[13] + Tree[13 - 1] + Tree[13 - 1 - 4]로 구할 수 있습니다. 이것을 보면 좀 재밌는 사실을 알 수 있습니다. Tree[13 - 1]에서 -1은 곧 13의 최하위 비트를 빼는 것이며, Tree[13 - 1 - 4]는 Tree[12 - 4]로 나타내면 4는 곧 12의 최하위 비트 4를 빼는 것입니다! 즉, 13(1101)에서 최하위 비트를 빼고 12(1100). 여기서 다시 최하위 비트를 빼면 8(1000)이 되어 [1, 13]의 구간합을 구할 수 있습니다.

 

바로 이러한 특징을 이용하여 펜윅트리를 구성하는 것입니다.