Fenwick 알고리듬(2)

Binary Indexed Tree 구조

앞에서 살펴본 테이블로 표시된 Fenwick 을 왜 Binary Indexed Tree 구조라고 부르는지 살펴볼 시간이다. 여기서도 0번 index에 해당하는 원소는 큰 의미가 없다. 살펴볼 것은 각각의 푸른 색 원소들은 모두 마지막 노드에 속해있고, (바로 앞의 원소의 값과 자신의 값의 부분합을 가지고 있는) 녹색의 원소는 그 푸른색의 원소만을 자녀 노드로 구성하고 있다. 

아래의 구조 내에서 처음 언급한 2개의 Operation이 어떻게 움직이는 지 다시 한번 살펴보자.

1) 부분 합을 가져와야 하는 경우 : Sum

만약 최초 배열의 0번부터 5번까지의 합을 가져와야 하는 경우라면, Fenwick 배열에서는 1번부터 6번까지의 배열 내의 값들의 합을 가져오면 된다. 이는 앞에 있는 모든 배열의 합을 더해야 할 필요없이 필요한 배열만 찾아내어서 그 합들을 더하면 된다.

즉 Sum(6) 을 Fenwick[1]번 부터 Fenwick[6]번까지의 합을 구하라는 함수라고 약속을 하면 다음과 같다.

Sum(6) = Fenwick[6] + Fenwick[4]

여기서 핵심은 Fenwick의 1번과 2번 그리고 3번이나 5번과 같은 배열 원소의 값은 바라볼(Lookup) 필요가 없다는 것이다.

계속해서 Sum(7) 을 구하고 싶으면 Fenwick[7] + Fenwick[6] + Fenwick[4] 이 된다. 연습삼아 Sum(5) 나 Sum(8) 을 구하려면 어떤 배열 값을 더할 지 그림을 통해 확인해 보고 확신이 들면 어느 정도 이 트리 구조에 조금씩 익숙해지기 시작하는 것이다.

Fenwick 배열을 트리 구조(Binary Indexed Tree)로 표현

2) 일부 노드의 값이 변경되는 경우 : Update

이제 일부 원소의 값이 변경되는 경우를 생각해보자.

만약 1번 원소의 값이 기존 3에서 4로 변경이 되어야 하는 경우라면, 이 상황에서도 모든 배열의 원소들이 같이 변경되어야 하는 것이 아니라 정확하게 필요한 원소들만 변경이 되면 된다. 여기서도 Update(1,4) 라는 함수의 약속을 Fenwick 배열에서 1번째 원소의 값을 4로 바꾸라는 명령어라고 약속을 하자.

그러면 오른 쪽 그림과 같이 자신의 원래 값 3을 부분합으로 가지고 있는 부모 노드 중 Fenwick[2] 와 Fenwick[4] 그리고 Fenwick[8]만 따라서 변경이 되면 된다. 마찬가지로 Update(3,7) 과 같이 3번째 원소의 값을 7로 변경해야 할 경우는 자기 자신  Fenwick[3]의 값을 원래 6에서 7로 변경하고 Fenwick[4]와 Fenwick[8]만 정확하게 변경을 해 주면 모든 문제가 해결된다.

여기서 우리가 생각해 보아야 할 것은 알고리듬은 어떻게 - 1번 원소에서 시작하는 경우나 3번 원소에서 시작하는 경우 - 정확하게 상위 부모 노드에 해당하는 4번과 8번을 알아서 찾을 수 있는가 하는 문제이다. 이제 실제로 index를 중심으로 필요한 해당 배열 원소들을 어떻게 추적하고 변경할 수 있는지 살펴보자.

(계속 설명을 하기 전에) 만약 이 트리 구조를 배우려고 처음 접하는 사람은 아래의 구조들에 대해서 조금 더 여유를 가지고 천천히 살펴볼 것을 추천한다. 이 구조에 익숙해 지는 것이 코딩 자체 보다도 더 많은 시간을 절약할 수 있기 때문이다. 

Index 추적 방법과 추적 예제 (1)

앞에서 말한 것과 같이 Update(1,4) 과 같이 1번째 원소의 값을 4로 변경할 경우, Fenwick[1]의 값을 원래 3에서 4로 변경하고 Fenwick[2]와 Fenwick[4], Fenwick[8] 만 정밀 타격을 하듯이 변경해주면 된다고 살펴보았다. 

즉 변경되어야 할 값이 3에서 4로 바뀌어야 되니까 그 변경 차이인 delta = 1 (= 4 - 3) 을 다음과 같이 순차적으로 변경해주면 된다.

Fenwick[1]	3 + 1 (delta) = 4
Fenwick[2]	8 + 1 (delta) = 9
Fenwick[4]	14 + 1 (delta) = 15
Fenwick[8]	35 + 1 (delta) = 36

이제 우리가 이해해야 하는 과정은 배열의 1번 원소의 값을 4로 변경하고 나서 그 다음 목표를 정확하게 어떻게 찾는가 하는 문제이다. 여기서 우리는 이진수 계산의 절차를 이해해야만 한다. 여기서 우리는 다음 수식(syntax)를 이해할 필요가 있다.

idx += idx & -idx

즉 아래의 도표와 같이, 처음 인덱스(idx)가 1번으로 시작을 했다면 다음 목표인 2가 이 함수의 결과로 나와야 한다. 마찬가지로 2번 인덱스가 입력일 경우, 이 함수의 결과는 4가 나와야 하며, 4를 넣으면 8이 나와야 한다.

index += index & -index 추적표

 

조금 더 자세하게 살펴보자. 이 함수는 대략 크게 3개의 단계로 세분할 수 있다. ① 자신의 값에 해당하는 이진수의 보수 (2's complement)를 구해야 한다.  ② 해당 보수와 원래의 자신의 이진수를 AND 연산자(&)를 이용하여 더해야 한다. 참고로 AND 연산자는 두 값이 모두 1 (또는 True)에 해당할 경우만 1(또는 True)의 값을 출력한다.  ③ AND 연산 결과를 다시 최초 이진수와 합하여 결과를 구한다.

최초 입력 값	1	2	4
idx	0001	0010	0100
① -idx	1 1 1 1      ( = 1110 + 1)	1110   (=1101 + 1)	1100 ( = 1011 + 1)
② idx & -idx	0001	0010	0100
③ idx + (idx & -idx)	0010  (= 0001 + 0001)	0100 (= 0010 + 0010)	1000 (= 0100 + 0100)
최종 출력 값	2	4	8

 

(계속)