펜윅나무

펜윅나무 이진 인덱스 트리
유형	바이오노말목
발명된	1989
발명자	보리스 랴브코
큰 O 표기법의 시간 복잡도
알고리즘. 평균 최악의 경우 공간 O(n) O(n) 서치 O(logn) O(logn) 삽입 O(logn) O(logn) 삭제 O(n) O(n)

이 글의 선두 부분은 그 내용을 충분히 요약하지 못할 수 있습니다. 위키백과의 리드 섹션 지침을 준수하기 위해 리드 섹션을 간결한 버전의 기사로 독립할 수 있도록 기사의 주요 요점에 대한 접근 가능한 개요를 제공하도록 수정하는 것을 고려해 주시기 바랍니다.(2023년 7월)

펜윅 트리(Fenwick tree) 또는 이진 인덱스 트리(BIT)는 값을 효율적으로 업데이트하고 값 배열에서 접두사 합을 계산할 수 있는 데이터 구조입니다.

이 구조는 1989년 보리스^[1] 랴브코(Boris Ryabko)에 의해 제안되었으며 1992년 ^[2]추가 수정이 발표되었습니다.1994년 ^[3]그의 기사에서 이 구조를 묘사한 피터 펜윅의 이름을 따서 펜윅 나무라는 이름으로 알려지게 되었습니다.

Fenwick 트리는 평평한 값 배열과 비교할 때 값 업데이트와 접두사 합 계산의 두 가지 작업 간에 훨씬 더 나은 균형을 유지합니다.n개의 ${\displaystyle$ n$}$ 값으로$$ $구성$된 플랫 어레이는 값 또는 접두사 합을 저장할 수 있습니다.첫 번째 경우, 계산 프리픽스 합은 선형 시간을 필요로 하고, 두 번째 경우, 배열 값을 업데이트하는 것은 선형 시간을 필요로 합니다(두 경우 모두 다른 연산은 일정한 시간 내에 수행될 수 있음).Fenwick 트리를 사용하면${\displaystyle }$O(${\displaystyle \log }$⁡ n$$){\$displaystyle O$(\log n$)}$ 시간 $내$에 두 작업을 모두 수행할 수 있습니다.이는 값을 ${\displaystyle \mathrm{n개}}$의${\displaystyle }$+ 1개의 ${\displaystyle$ n$+1}$개의$$ 노드가 $있는{\displaystyle }$ 트리로 나타내므로 트리의 각 노드의 값은 상위(포함) 인덱스에서 노드(전용) 인덱스까지의 배열의 접두사 합입니다.트리 자체는 암시적이며 n개의$${\$displaystyle$ n$}$ $값$의 배열로 저장할 수 있으며, 배열에서 암시적 루트 노드가 생략됩니다.트리 구조를 사용하면 O${\displaystyle (\log }$ ⁡${\displaystyle n}$ )$${\$displaystyle$ O$(\log$ n$)}$ 노드 $액세스$만 사용하여 값 검색, 값 업데이트, 접두사 합 및 범위 합 작업을 수행할 수 있습니다.

동기

값 배열이 주어지면 일부 연관 이진 연산에 따라 각 인덱스까지의 값의 실행 합계를 계산하는 것이 좋습니다(정수의 덧셈이 단연코 가장 일반적임).Fenwick 트리는 기본 값 배열에 대한 변경 사항을 허용하고 모든 추가 쿼리가 이러한 변경 사항을 반영하도록 하는 것 외에도 어떤 인덱스에서도 실행 중인 총합을 쿼리할 수 있는 방법을 제공합니다.

펜윅 트리는 특히 산술 코딩 알고리즘을 구현하도록 설계되어 있는데, 산술 코딩 알고리즘은 생성된 각 심볼의 카운트를 유지하고 이를 주어진 심볼보다 작은 심볼의 누적 확률로 변환해야 합니다.지원하는 운영 개발은 주로 이 경우에 사용하는 것이 동기부여가 되었습니다.

묘사

펜윅 트리는 n개의$${\$displaystyle$ n$}$개의$$ 값을 $가진{\displaystyle }$ 하나의 기반 $배열{\displaystyle }$ A${\displaystyle [n]}${\$displaystyle$ A$[n]}$을(를) 고려함으로써 가장 쉽게 이해할 수 있습니다.해당 펜윅 트리에는 암시적 노드가 0인 ${\displaystyle \mathrm{n개}}$의 ${\displaystyle$ n$+1}$개의$$ 노드가 $있습니다{\displaystyle }$.트리의 각 $수준$ k ${\displaystyle$k}에는 k ${\displaystyle$ k$}$의 서로 다른 거듭제곱이 2인 합에 해당하는 인덱스가 있는 노드가 포함되어 있습니다($빈$ 합이 0인 k = ${\displaystyle 0}${\$displaystyle$ k=$0}$ 포함).예를 들어 $수준$ k = ${\displaystyle 1}${\$displaystyle$ k=$1}$에 $노드$ 1 = ${\displaystyle {20}^{}}$ ${\displaystyle 2}$ = ${\displaystyle {21}^{}}$ ${\displaystyle 4}$ = ${\displaystyle 2^{}}$, ${\displaystyle$ 1=$2^{0}, 2$=$2^{1},$4=$2^{2},...$$}$$수준$ k $=$ ${\displaystyle 2}${\$displaystyle$ k$=$$2}$에 $노드$ 3 $=$ ${\displaystyle {}^{}}$ ${\displaystyle 1^{}}$+ ${\displaystyle {20}^{}}$ ${\displaystyle 5}$ $=$ ${\displaystyle {}^{}}$ +${\displaystyle {}^{}{20}^{}}$ ${\displaystyle 6}$ $=$ ${\displaystyle 2^{}}$+ ${\displaystyle 2^{}}$ ${\displaystyle {}^{},}$ ... ${\displaystyle$ 3$=$$2^{1}+2^{0}, 5$$=$$2^{2}+2^{0},$6$=$$2^{2}+2^{1},...$$}$주어진$$ 노드의 부모는 인덱스의 마지막 설정 비트(LSB)를 지움으로써 찾을 수 있으며, 이는 합에서 2의 최소 거듭제곱에 해당합니다.예를 들어 6 = 110의 부모는 4 = 100입니다.

다음 다이어그램은 15개 요소 배열 A에 해당하는 16개 노드 펜윅 트리의 구조를 보여줍니다.

A${\displaystyle }$(${\displaystyle i,j}$ ] = {${\displaystyle A}$ [${\displaystyle k}$ ]${\displaystyle {}_{}^{}}$} ${\displaystyle k_{}^{}}$ =${\displaystyle i_{}^{}}$ + ${\displaystyle 1_{}^{}}$ ${\displaystyle {}_{}^{}}${\$displaystyle$ A$(i,j$]=\{라고 $합니다$.$A[k]\}_{k=i+1}^{j$$인덱스{\displaystyle }$ i$${\$displaystyle$ i$}$의 노드 값은 A$]$ {\$displaystyle$ A$(\mathrm {parent}(i),i$의 값 범위 합에 해당합니다. 즉, 현재 노드의 인덱스까지 부모 인덱스 다음으로 시작하는 A의 값입니다.$값$ A${\displaystyle (\mathrm{parent}}$(${\displaystyle i),i}$ ]$${\$displaystyle$ A$(\mathrm {parent}(i),i]}$는 현재 노드에 대한 "책임 범위"로 되며 (i )= (i (-$)$ {\$mathrm {lsb}(i$)= $(i$\ $\&\(i))}($여기서 & 는 비트와이즈 AND를 나타냅니다) 값으로 됩니다.이 범위의 인덱스는 i$${\$displaystyle$ i$\}$의 하위 인덱스와 직접적으로 일치하지 않습니다. 예를 들어 노드 2의 책임 $범위$는 A${\displaystyle (0,}$ ${\displaystyle 2]}$ = {${\displaystyle A}$ ${\displaystyle [1],A}$ [${\displaystyle 2]}$ $}$ {\$displaystyle$ A$(0,$2]=\{$A[1],$$A[2]\}:$ 그러나$$ 노드 1은 노드 2의 자식이 아닙니다.루트 노드 0에는 값이 0인 빈 $범위$ A${\displaystyle (0,0}$ ] = { } {\$displaystyle$ A$(0,0$]=\{\})의 합이 포함되어 있습니다.

값 배열을 통해 펜윅 트리를 구축하는 초기 프로세스는 O${\displaystyle (n}$ logon${\displaystyle )}${\$displaystyle O(nlogn$)} 시간$$ $내$에 실행됩니다.

최대/분 범위 쿼리

인덱스 = ${\displaystyle {}^{}}$ 2 ${\displaystyle i^{}}${\$displaystyle k2^{i}($k는 홀수)(k는 홀수)인 다음 간격으로 min/max를 추적하면 [${\displaystyle l,}$r]$${\$displaystyle [l,r]}$ 범위에서$$max/min을 찾을 수 있습니다.

${\displaystyle BIT1[i]=[(k-1)2^{i}+1,k2^{i}]}$

${\displaystyle BIT2[i]=[k2^{i},(k+1)2^{i}-1]}$

이것은 다음을 의미합니다.

• 하위 트리의 첫 번째 노드에서 이 노드까지 모든 노드를 한 번 보고 왼쪽 자식을 따라 리프 노드를 칠 때까지 이동합니다.왼쪽 자식이 없으면 위치를 변경하지 않습니다.

• 이 하위 트리의 위치 오른쪽에 있는 모든 노드를 보면 루트 노드를 제외한 부분 트리의 일부입니다.

특별한 경우는 BIT1과 BIT2의 일부인 $노드{\displaystyle }$ i {\$displaystyle$ k2$^{i$가 max/min인 경우입니다.

주요 아이디어:max가 BIT1과 BIT2에 모두 있는 경우 루트 노드여야 합니다.그렇지 않으면 왼쪽이나 오른쪽에 있습니다.어떤 시점에서, 사람들은 max가 리프 노드 또는 루트 노드라는 것을 마주치게 될 것입니다; 이러한 사고방식을 반복함으로써.

트리를 구축할 때, 각 값에 대해 BIT1, BIT2 또는 둘 다에 있는지 확인합니다.BIT1[i]에 있으면 ${\displaystyle \mathrm{BIT1}[i]}$ = ${\displaystyle \max }$ ${\displaystyle (\mathrm{BIT1}[i],}$ ${\displaystyle A[i])}${\$displaystyleBIT1[i$]=$max(B$)$IT1[i],$A$[i$ BIT2도 $마찬가지$입니다.이후 인덱스를 val = val + val & (-val)로 업데이트합니다.배열의 SIZE가 적중될 때까지 반복합니다.

[${\displaystyle l,r]}$ ${\displaystyle[l,r]}$ 범위$$ 검색을${\displaystyle }$수행할 때는 값이 합법적인 범위 내에 포함되지 않은 BIT1 및 BIT2로 들어가지 않아야 합니다.

일반${\displaystyle }$[${\displaystyle 0,r}$ ]$${\$displaystyle[0,r]}$ max$$/min 쿼리는 합/곱과 동일한 방식으로 구현할 수 있습니다.

총 범위 쿼리

[0,r]에서 범위 합에서 2^i = (-val) & val; 1을 빼서 모든 오른쪽 부모를 우회한 후 첫 번째 왼쪽 부모로 이동합니다.그 다음엔 아이에게, 아이가 어디서 왔는지와 가장 가까운 지수를 가지고 있습니다.왼쪽 아이들을 아래로 향하게 하고, 아래로 향하게 하고, 그렇지 않으면.한 사람은 두 번 더 추가하는 것을 피합니다. 한 사람은 항상 왼쪽으로 가고, 결코 오른쪽으로 가지 않기 때문입니다. 한 사람은 오른쪽에 추가만 됩니다(index, delta).

어떤 일이 일어나고 있는지는 하위 트리의 가장 가까운 루트로 이동하는 것입니다. 그 다음에 하위 트리의 가장 가까운 루트로 이동하는 것입니다. 그 다음에 하위 트리의 가장 많은 값을 포함하는 노드에서 하위 인덱스로 이동합니다. 같은 하위 트리에 하나가 있습니다.하위 트리를 덮기 위해 루트의 여러 자식을 통과할 수도 있습니다.이 하위 트리가 가려지면 한 사람은 더 큰 하위 트리로 이동합니다.만약 어떤 사람이 어린아이에게 내려가지 않았다면, 지수 1에 대해 오른쪽으로 가는 위험을 감수했을 것입니다. 이는 2^i = (-val) & valto - 를 빼면 같은 값이 두 번 더 추가된다는 것을 의미합니다.

맨 아래로 내려가지 않았다면, 먼저 왼쪽 아이에게 가야 할 때, 같은 가치를 여러 번 더할 위험을 감수했을 것입니다.

[l,r] 범위 합을 구하려면 합(0,r) - 합(0,l)만 구하면 됩니다.

합산포인트업데이트

$인덱스{\displaystyle }$ i$${\$displaystyle$ i$\}$의 펜윅 트리의 값을 업데이트하려면 다음을 수행합니다.

• 델타 δ$$= $A$[$i_{}$ ] ${\mathrm{new}}_{}$ ${-}_{}$A [$i_{}$ ] ${\mathrm{old}}_{}${\$textstyle \delta$ = $A[i]_{\mathrm${new$}}-A[i]_{\mathrm${old$\}\}\}$을(를) 계산합니다.
• 그러면 $인덱스{\displaystyle }$ i ${\displaystyle \le }$ ${\displaystyle n}$ ${\displaystyle$ i$\leqn$인 반면:
  • LSB를 추가하여 인덱스 업데이트: ←+ (&( -i){\$displaystyle$ i$\leftarrow$ i$+(i\ \&\(-i))}$
  • i $노드$ ${\displaystyle$ i$\}$의 값에$$δ {\$displaystyle \delta}$을(를) 추가합니다.

값을 더할 때는 항상 오른쪽으로 가야 합니다. 왜냐하면 합을 항상 왼쪽으로 두면 같은 값을 두 번 합하는 위험을 피할 수 있기 때문입니다.

2^i = -val & val을 더할 때, 가장 가까운 부모로 간단히 이동합니다.

트리 만들기

다음과 같이 진행합니다.

• $배열{\displaystyle }$ A${\displaystyle [n]}${\$displaystyle$ A$[n]}$을(를) 트리 값이 포함된$$ $배열{\displaystyle }$ T${\displaystyle [n]}${\$displaystyle$ T$[n]}$로 복사합니다.
• 각 인덱스 i에 대해 1부터 n까지:
  • j =+ (&( -) ${\displaystyle$ j=$i+(i\ \&\(-i$라고 .이 노드는 책임 범위에 A$]$ {\$displaystyle$ A$[i]}$이(가$$) $포함$된$$i {\$displaystyle$ i$}$보다 큰 첫 번째 노드입니다.
  • j ${\displaystyle \le }$ ${\displaystyle n}$ ${\displaystyle$ j$\leqn$인 경우 j에서 노드의 업데이트 값:${\displaystyle }T$ [${\displaystyle j}$ ] ←${\displaystyle T}$ [${\displaystyle j}$] +${\displaystyle T}$ [${\displaystyle i}$ ]$${\$displaystyle$ T$[j]\leftarrow$ T$[j]+$$T[i]}$

각 업데이트는 인덱스당 최대 한 번 발생하므로 결과 알고리즘은 O${\displaystyle (n)}${\$displaystyle$ O$(n)}$ 시간$$ $복잡도$입니다.이 작업은 원래 배열에서 제자리에서 수행할 수도 있으므로 T$[$ {\$displaystyle$T$[$n]}에 $대한{\displaystyle }$ 복사 및 추가 저장소가 제거됩니다.

유사한 작업을 수행하여 n에서 1로 역반복하고 각 시간 단계에서$$i {\$displaystyle$i}의 값에서 =i + (i &(-i) {\$displaystyle j$=$i$ + ($i\ \&\(-i$))}의 값을 빼서 Fenwick 트리를 $원래$의 주파수 배열 A${\displaystyle [n}$ ] {\$displaystyle$ A$[$n${\displaystyle ]}${\displaystyle A$[n$로 다시 변환할 수 있습니다.

다차원으로 확장

2D 펜윅 트리(2D BIT)는 트리의 각 노드가 1D 펜윅^[5] 트리를 포함하고 2D 행렬 A[m,n]의 하위 행렬에 대한 범위 합을 저장하는 1D 펜윅 트리로 구성될 수 있습니다.트리 표현은 암시적으로 유지되며 데이터는 배열의 위치 (i, j)가 i번째 펜윅 트리의 j번째 노드에 해당하는 mxn 배열에 저장됩니다.

점 업데이트 및 범위 쿼리는 1D 경우와 유사하게 구현되지만 중첩 루프(내부 루프의 열 차원(하위 트리)을 따라 반복하고 외부 루프의 행 차원(메인 트리)을 따라 반복)를 사용합니다.

이 아이디어는 범위 쿼리 및 포인트 업데이트(텐서가 각 축을 따라 크기 n이라고 가정)를 위한 시간 $복잡도$ O${\displaystyle ({log}^{}}$ ${\displaystyle d{}^{}}$⁡ n ) ${\displaystyle$ O$(\log ^{d}$n$)}$와 함께 임의의 수의 차원 d를 가진 텐서로 확장될 수 있습니다.

의사코드

펜윅 트리에서 두 가지 주요 연산인 쿼리와 업데이트의 간단한 의사코드 구현은 다음과 같습니다.

함수 쿼리(tree, index)는 합 := 0인 반면 인덱스 > 0 도합 += tree[index] 인덱스 -= lso(index) 반환 합 함수 업데이트(tree, index, value)는 인덱스 < size(tree) do tree[index] += value 인덱스 += lso(index)입니다.

함수${\displaystyle \text{lso}}$ (${\displaystyle$ {\text${lso}}(n)$은 $주어진$ n ${\displaystyle$ n$}$의 최하위 1비트 또는 마지막 집합 비트를 계산하거나, n ${\displaystyle$ n$\}$의 약수이기도 한 2의 최대 거듭제곱을 계산합니다. 예를 들어 ${\displaystyle \text{lso}}$(${\displaystyle 20)}$ = ${\text{lso}(20$) =$4$이진법 표현과 같이 ${\displaystyle \text{lso}}$(${\displaystyle 10}$ ${\displaystyle {100}_{}}$ 2${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle 100}$ 2 =$$4 {\$displaystyle {\text{lso}}(10{\textbf {$1}}, 00_${2$}) =$100_${2}= $4$입니다.이 기능은 비트 와이즈 AND 연산을 통해 간단히 코드로 구현할 수 있습니다.lso(n) = n & (-n), 부호가 있는 정수 데이터 ^[3]유형을 가정합니다.

시공

펜윅 트리를 구성하기 위한 하나의 순진한 알고리즘은 널 값으로 트리를 초기화하고 각 인덱스를 개별적으로 업데이트하는 것으로 구성됩니다.이 솔루션은 O${\displaystyle (n}$ log ⁡${\displaystyle n}$ )$${\$displaystyle$ O$(n\log$ {$n})}$ 시간 $내$에 작동하지만 O${\displaystyle (n)}${\$displaystyle$ O$(n)}$ $구성$이 가능합니다.

함수 구성(값)은 모든 인덱스에 대한 트리 := 값이며 트리의 상위 값입니다.인덱스 : = 인덱스 + ls(인덱스)(부모인 경우)인덱스 < 크기(트리) 다음 트리[부모]인덱스] += 값 반환 트리

적용들

이 섹션에는 여러 가지 문제가 있습니다.개선을 도와주시거나 토크 페이지에서 이 문제들을 논의해 주시기 바랍니다.(이 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 절에서는 출처를 언급하지 않습니다. 신뢰할 수 있는 자료에 인용문을 추가하여 이 부분을 개선하는 데 도움을 주시기 바랍니다. 출처가 밝혀지지 않은 자료에 이의를 제기하여 제거할 수 있습니다.(2023년 7월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 섹션의 어조 또는 스타일은 위키피디아에서 사용되는 백과사전적인 어조를 반영하지 못할 수 있습니다. 제안은 위키피디아의 더 나은 기사 작성 가이드를 참조하십시오.(2023년 7월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

가장 긴 연속 증가

배열 $[{\displaystyle 8,}$ ${\displaystyle 5,}$ ${\displaystyle 7,}$ ${\displaystyle 3,}$ ${\displaystyle 1,}$ ${\displaystyle 2,}$ ${\displaystyle 9,}$ ${\displaystyle 4,}$ ${\displaystyle 6]}${\$displaystyle [8,$ 5,$7, 3,$1, 2, $9,$4, 6] {\displaystyle [8, 5, 7, 3, 1, 2, 4, 6$]}$을(를) 고려합니다.

각 $항목$에 대해${\displaystyle }$A$]$ {\$displaystyle A[i$]}:

] $=$ < ){\$displaystyle$ $[i$]=$max(0\leq$ x$<i)}$${\displaystyle }$ [${\displaystyle x}$] + ${\displaystyle 1}${\$displaystyle$ A$[x]$ +$1$ s.t. array[] <= array[i].

array[x] <= array[i]>는 i = array[index in list]이기 때문에 보장됩니다.

실행 예제:

1. A[array[0] = A[8] = 최대값(0 <= x < 8) A[x] + 1 = 최대값(0,0,0,0,...,0) + 1 = 1
2. A[array[1] = A[5] = 최대값(0 <= x < 5) A[x] + 1 = 최대값(0,0,0,0,0,...,0) + 1 = 1
3. A[array[2] = A[7] = 최대값(0 <= x < 7) A[x]+ 1 = 최대값(A[0],[1],A[2],A[3],A[4],A[5],A[6]) + 1 = A[5] + 1 = 1 + 1 = 2
4. A[array[3] = A[3] = 최대값(0 <= x < 3) A[x] + 1 = 최대값(0,0,0...,0) + 1 = 1
5. A[array[4] = A[1] = 최대값(0 <= x < 1) A[x] + 1 = 최대값(A[0]) + 1 = 1
6. A[array[5]] = A[2] = 최대값(0 <= x < 2) A[x] + 1 = 최대값(0,1) + 1 = 2
7. A[array[6] = A[9] = 최대값(0 < x < 9) A[x] + 1 = 최대값(0,1,2,1,0,1,0,2,1) + 1 = 2+1 = 3
8. A[array[7] = A[4] = 최대값(0 <= x < 4) A[x] + 1 = 최대값(0,1,2,1) + 1 = 2+1 = 3
9. A[array[8] = A[6] = 최대값(0 < x < 6) A[x] + 1 = 최대값(0,1,2,1,3,1) + 1 = 3+1 = 4

그것은 정답 1,2,4,6에 잘 해당합니다.

최대값이 너무 크면 정렬을 사용하여 숫자 압축을 사용할 수 있습니다.

i = 배열[정렬되지 않은 목록의 인덱스] 대신 i = indexInSortedList[정렬되지 않은 목록의 인덱스]입니다.

예를 들어 다음과 같습니다.

• 배열: 166,32,44,66,88
• 분류: 32,44,66,88,166

그러면:

A[indexInSortList[0]] = A[4] 이제 우리는 익숙한 문제로 돌아갑니다.

참고 항목

• 주문통계 트리
• 접두사 합
• 세그먼트 트리

참고문헌

외부 링크

• 탑코더의 펜윅 나무에 대한 튜토리얼
• 알고리즘리스트에 관한 펜윅 트리에 관한 글
• Polymath 위키의 Penwick Tree 항목
• 스택 교환