펜윅 트리

**펜윅 트리**(Fenwick tree) 또는 **이진 인덱스 트리**(binary indexed tree, **BIT**)는 값의 배열을 저장하고 값의 누적 합을 효율적으로 계산하며 값을 업데이트할 수 있는 자료 구조이다. 또한 지정된 값 이하의 합계를 가진 가장 긴 접두사를 찾기 위한 효율적인 순위 검색 연산도 지원한다. 주로 자주 업데이트되는 통계 빈도 테이블의 누적 분포 함수에 대해 작동하는 데 사용된다.

이 구조는 1989년 보리스 랴프코가 제안했으며 1992년에 추가 수정이 발표되었다. 이후 피터 펜윅이 1994년 논문에서 이 구조를 설명한 후 펜윅 트리라는 이름으로 알려지게 되었다.

값의 단순 배열은 업데이트하기 쉽지만(상수 시간) 누적 합을 계산하거나 접두사 길이를 검색하는 데는 O(n) 시간이 필요하다.

누적 합 배열은 상수 시간에 누적 합을 반환하고, O(\log n) 시간에 접두사 길이를 검색할 수 있지만, 값 중 하나를 업데이트하는 데는 O(n) 시간이 필요하다.

펜윅 트리는 세 가지 작업을 모두 O(\log n) 시간에 수행할 수 있다. 이는 값을 n+1개의 노드를 가진 트리로 표현하여 각 트리의 노드가 해당 부모 노드의 인덱스(배타적)부터 해당 노드의 인덱스(포괄적)까지의 값의 합을 저장함으로써 달성된다. 트리는 그 자체가 암시적 자료 구조이며 n개의 값 배열로 저장될 수 있으며, 암시적 루트 노드는 배열에서 생략된다. 트리 구조는 값 검색, 값 업데이트, 누적 합 및 범위 합 작업을 O(\log n) 노드 액세스만을 사용하여 수행할 수 있도록 한다.

## 동기
값의 배열이 주어졌을 때, 때로는 특정 결합적이항 연산 (정수의 덧셈이 가장 흔함)에 따라 각 인덱스까지의 값의 누적 합을 계산하는 것이 바람직하다. 펜윅 트리는 기본 값 배열의 변경을 허용하고 모든 후속 쿼리가 이러한 변경을 반영하도록 하면서, 어떤 인덱스에서든 누적 합 또는 접두사 합을 쿼리하는 방법을 제공한다.

펜윅 트리는 적응형 산술 부호화를 구현하는 데 특별히 고안되었는데, 이는 생성된 각 심볼의 수를 유지하고 이를 주어진 심볼보다 작은 심볼의 누적 확률로 변환해야 한다. 지원하는 연산의 개발은 주로 이 경우의 사용에 동기가 부여되었다.

## 설명
펜윅 트리는 노드가 연속적으로 번호가 매겨지고, 부모-자식 관계가 노드 인덱스에 대한 산술 연산으로 결정되는 암시적 자료 구조이다.

이 인덱스 산술에서 중요한 함수는 최하위 비트이다. 이는 인덱스 i를 나누는 가장 큰 2의 거듭제곱이다. 이는 지수(0, 1, 2, 3, ...)가 아닌 2의 거듭제곱(1, 2, 4, 8, ...)이다. 2의 보수 산술에서 \operatorname{lsb}(i) = i\mathbin\& -i (여기서 &는 비트 AND를 나타냄)로 효율적으로 계산할 수 있다.

펜윅 트리는 1-기반 배열 A[n]에 n개의 값을 사용하여 가장 쉽게 이해된다. 반개방 구간 표기법을 사용하여 A(i,j] = \{ A[k] \}_{k=i+1}^j,는 i(배타적)부터 j(포괄적)까지의 범위를 나타낸다. 해당 펜윅 배열 F[n]은 범위 합 \textstyle F[i] = \sum A(i-\operatorname{lsb}(i),i]를 저장한다. 즉, A[i]를 포함하여 끝나는 \operatorname{lsb}(i)개 값의 합이다.

일부 설명에서는 가상의 노드 0이 사용되지만, 실제로는 액세스되지 않으며 명시적으로 저장할 필요가 없다. \operatorname{lsb}(0) = \infty,이지만 이 값은 실제로는 필요하지 않다. F[0]은 값 0을 가진 빈 범위 A(0,0] = \{\}의 합을 포함하는 것으로 간주될 수 있다.

"펜윅 트리"는 실제로는 동일한 배열에 대한 세 가지 암시적 트리를 의미한다: 인덱스를 접두사 합으로 변환하는 데 사용되는 쿼리 트리, 요소를 업데이트하는 데 사용되는 업데이트 트리, 그리고 접두사 합을 인덱스로 변환하는 데 사용되는 검색 트리(순위 쿼리). 처음 두 트리는 일반적으로 위로 이동하며, 세 번째 트리는 일반적으로 아래로 이동한다.

### 쿼리 트리
쿼리 트리는 노드 i의 부모가 i - \operatorname{lsb}(i) = i \mathbin\& (i-1)가 되도록 정의된다. 예를 들어, 6 = 1102의 부모는 4 = 1002이다. 암시적 노드 0은 루트이다.

트리의 각 레벨 k는 k개의 고유한 2의 거듭제곱 합에 해당하는 인덱스를 가진 노드를 포함한다(k=0은 빈 합 0을 나타냄). 예를 들어, 레벨 k=1은 노드 1=2^0, 2=2^1, 4=2^2, ...를 포함하고 레벨 k=2는 노드 3=2^1 + 2^0, 5 = 2^2 + 2^0, 6 = 2^2 + 2^1, ...를 포함한다.

노드 i는 \log_2(\operatorname{lsb}(i))개의 자식(i+1, i+2, i+4, ..., i+\operatorname{lsb}(i)/2)을 가지며, 총 \operatorname{lsb}(i)개의 자손을 가진다. (이 숫자에는 n보다 큰 노드가 포함되며, 이 노드들은 생략되고 액세스되지 않는다.)

아래 다이어그램은 16개 노드 펜윅 트리의 쿼리 트리의 구조를 보여주며, 루트를 포함하므로 15개 요소 배열 A에 해당한다:
center|섬네일|438x438px|15개 노드 배열 A의 범위 합을 포함하는 16개 노드 펜윅 쿼리 트리의 묘사

누적 합 A[1] + \cdots + A[i]를 찾으려면, i와 그 부모, 부모의 부모 등 루트(포함하지 않음)까지의 값을 더한다. 범위 합 A[i] + \cdots + A[j]를 계산하려면, i-1과 j에 대한 누적 합을 뺀다.

이는 첫 번째 공통 조상에서 멈춤으로써 최적화될 수 있다. 극단적인 예는 단일 엔트리 A[j]를 요청하는 것이다. 이 경우, j와 i = j-1의 공통 조상은 j - \operatorname{lsb}(j)이므로, F[j]에서 시작하고 i \neq j - \operatorname{lsb}(j)인 동안 F[i]를 빼고 `i := i - lsb(i)`로 업데이트한다.

### 업데이트 트리
업데이트 트리는 쿼리 트리의 거울상이다. 노드 i의 부모는 i + \operatorname{lsb}(i) = (i \mathbin| (i - 1)) + 1이다 (여기서 |는 비트 OR을 나타냄). 예를 들어, 6 = 1102의 부모는 8 = 10002이다.

이 개념적인 트리는 무한하지만, n까지의 인덱스를 가진 부분만 저장되거나 사용된다. n보다 큰 인덱스를 가진 가상의 노드를 제외하면, n의 이진 표현에서 설정된 각 비트에 대해 하나의 분리된 트리의 숲이 된다.

여기서 노드의 조상은 자신의 범위 합을 포함하는 모든 노드이다. 예를 들어, F[6]은 A(4,6]의 합을 포함하고, F[8]은 A(0,8]의 합을 포함한다.

A[i]의 값 중 하나를 수정하려면, F[i]에 변경 사항을 더한 다음, i의 부모, 그 다음 조부모 등으로 인덱스가 n을 초과할 때까지 계속한다.

### 검색 트리
다른 두 트리와 달리, 검색 트리는 이진 트리이며 커누스가 "옆으로 된 힙"이라고 부르는 순서로 배열된다. 각 노드에는 인덱스의 이진 표현에서 후행 0의 수와 동일한 높이가 할당되며, 부모와 자식은 인접 높이의 수치적으로 가장 가까운 인덱스이다. 홀수 인덱스(\operatorname{lsb}(i) = 1)를 가진 노드는 리프이다. 짝수 인덱스를 가진 노드는 다음 최저 인덱스의 가장 가까운 두 노드를 자식으로 가지며, i \pm \operatorname{lsb}(i)/2이다. 검색 트리에서 노드 i의 부모는 (i - \operatorname{lsb}(i)) \mathbin| (2 \cdot \operatorname{lsb}(i))이다.

예를 들어, 6 = 1102의 자식은 5 = 1012와 7 = 1112이며, 부모는 4 = 1002이다.

이 트리는 잠재적으로 무한하지만, 우리는 그 루트를 n보다 작거나 같은 2의 가장 큰 거듭제곱인 가장 높은 기존 노드로 정의할 수 있다.

노드가 n보다 큰 인덱스를 가진 가상의 부모를 가질 수 있지만 여전히 기존의 조부모를 가질 수 있다. 위 예제가 5개 노드 트리에 적용된다면, 노드 5는 가상의 부모 6을 가지지만, 기존의 조부모 4를 가진다.

검색 트리는 이전 두 트리의 조합으로 간주될 수 있다. 노드의 왼쪽 서브트리는 업데이트 트리의 모든 자손을 포함하고, 오른쪽 서브트리는 쿼리 트리의 모든 자손을 포함한다. 검색 트리에서 노드의 부모는 쿼리 또는 업데이트 부모(노드가 각각 오른쪽 또는 왼쪽 자식인지에 따라 다름)이며, 다른 유형의 부모는 검색 트리에서 여러 번 위로 이동하여 찾을 수 있다.

그러나 검색 트리에서 위로 이동하는 경우는 드물며, 주로 순위 쿼리를 수행하는 데 사용된다: 주어진 접두사 합이 어떤 인덱스에 나타나는가? 이는 검색 트리를 아래로 이동하여 수행된다. 이동 중에 세 가지 변수가 유지된다: 현재 노드의 인덱스, 현재 노드를 루트로 하는 서브트리에서 찾는 순위, 그리고 찾는 순위가 서브트리에서 찾을 수 있는 것보다 클 경우 반환될 "폴백 인덱스"이다.

초기에는 현재 노드가 루트이고, 찾는 순위가 원래 쿼리이며, 폴백 인덱스는 순위가 트리에 없음을 나타내는 특별한 "오버플로" 값이다. (응용 프로그램에 따라 0 또는 n+1이 이 목적으로 사용될 수 있다.)

각 단계에서 현재 노드가 가상의 노드(인덱스가 n보다 큼)이거나, 찾는 위치가 현재 노드의 끝의 왼쪽 또는 오른쪽인지 결정해야 한다. 찾는 순위가 현재 노드에 대한 펜윅 배열 값 F[i]보다 작으면 왼쪽 서브트리를 검색해야 한다. 크면 오른쪽 서브트리를 검색한다. 같으면 선택된 방향은 두 노드 사이에 정확히 있는 합계를 검색하는 방법을 처리하는 방법에 따라 달라진다.

이 세 가지 가능성은 현재 노드가 리프인지 아닌지에 따라 추가로 나뉜다:
* 현재 노드가 리프이고:
** 대상이 (빈) 왼쪽 서브트리에 있으면 현재 인덱스를 반환한다.
** 가상이거나 대상이 오른쪽 서브트리에 있으면 폴백 인덱스를 반환한다.
* 현재 노드가 리프가 아니고:
** 가상이면 변경되지 않은 폴백 인덱스로 왼쪽 서브트리에서 동일한 순위를 검색한다.
** 대상이 왼쪽 서브트리에 있으면 현재 인덱스를 폴백 인덱스로 사용하여 왼쪽 서브트리에서 동일한 순위를 검색한다.
** 대상이 오른쪽 서브트리에 있으면 변경되지 않은 폴백 인덱스로 오른쪽 서브트리에서 현재 노드의 값을 뺀 대상 순위를 검색한다.

## 의사코드

펜윅 트리의 두 가지 주요 연산(쿼리 및 업데이트)에 대한 간단한 의사코드 구현은 다음과 같다:

 **function** query(tree, index) **is**
     sum := 0
     **while** index > 0 **do**
         sum += tree[index]
         index -= lsb(index)
     **return** sum

 **function** update(tree, index, value) **is**
     **while** index \text{lsb}(n)은 주어진 n의 최하위 비트를 계산하거나, 동일하게 n의 약수이기도 한 가장 큰 2의 거듭제곱을 계산한다. 예를 들어, \text{lsb}(20) = 4는 이진 표현에서 보듯이: \text{lsb}(10\textbf{1}00_2) = 100_2 = 4이다. 이 함수는 2의 보수 부정을 가정할 때 비트 AND 연산을 통해 코드에서 간단히 구현될 수 있다: `lsb(n) = n & (-n)`.

### 생성

펜윅 트리를 구성하는 한 가지 비효율적인 알고리즘은 트리를 널 값으로 초기화하고 각 인덱스를 개별적으로 업데이트하는 것이다. 이 해결책은 O(n\log{n}) 시간에 작동하지만, O(n) 구성도 가능하다:

 **function** construct(values) **is**
     tree := values
     **for** index **from** 1 **to** size(tree) **do**
         parentIndex := index + lsb(index)
         **if** parentIndex &leq; size(tree) **then**
             tree[parentIndex] += tree[index]
     **return** tree

## 같이 보기
* 순서 통계 트리
* 누적 합
* 세그먼트 트리

## 각주

## 외부 링크
* TopCoder의 펜윅 트리 튜토리얼
* Algorithmist의 펜윅 트리 문서
* Polymath 위키의 펜윅 트리 항목
* 스택 익스체인지

분류:러시아의 발명품
분류:소련의 발명품
분류:트리 구조