logo

이진 인덱스 트리 또는 펜윅 트리

이진 인덱스 트리를 이해하기 위해 다음 문제를 고려해 보겠습니다.
arr[0 배열이 있습니다. . . n-1]. 우리는
1 처음 i개 요소의 합을 계산합니다.
2 배열 arr[i] = x의 지정된 요소 값을 수정합니다. 여기서 0 <= i <= n-1입니다.
간단한 해결책 0에서 i-1까지 루프를 실행하고 요소의 합을 계산하는 것입니다. 값을 업데이트하려면 arr[i] = x를 수행하면 됩니다. 첫 번째 작업에는 O(n) 시간이 걸리고 두 번째 작업에는 O(1) 시간이 걸립니다. 또 다른 간단한 해결책은 추가 배열을 만들고 이 새 배열의 i번째 인덱스에 있는 첫 번째 i번째 요소의 합계를 저장하는 것입니다. 주어진 범위의 합은 이제 O(1) 시간 안에 계산될 수 있지만 업데이트 작업에는 이제 O(n) 시간이 걸립니다. 이는 쿼리 작업 수가 많지만 업데이트 작업 수가 매우 적은 경우에 잘 작동합니다.
O(log n) 시간 안에 쿼리와 업데이트 작업을 모두 수행할 수 있습니까?
효율적인 솔루션 중 하나는 O(Logn) 시간에 두 작업을 모두 수행하는 세그먼트 트리를 사용하는 것입니다.
대체 솔루션은 두 작업 모두에 대해 O(Logn) 시간 복잡도를 달성하는 Binary Indexed Tree입니다. 세그먼트 트리와 비교하여 이진 인덱스 트리는 공간이 덜 필요하고 구현하기가 더 쉽습니다. .
대표
이진 인덱스 트리는 배열로 표현됩니다. 배열을 BITree[]로 둡니다. 이진 인덱스 트리의 각 노드는 입력 배열의 일부 요소의 합계를 저장합니다. 이진 인덱스 트리의 크기는 n으로 표시되는 입력 배열의 크기와 같습니다. 아래 코드에서는 구현의 용이성을 위해 n+1 크기를 사용합니다.
건설
BITree[]의 모든 값을 0으로 초기화합니다. 그런 다음 모든 인덱스에 대해 update()를 호출합니다. update() 작업은 아래에서 설명합니다.
운영

getSum(x): 하위 배열 arr[0,…,x]의 합계를 반환합니다.
// arr[0..n-1]에서 생성된 BITree[0..n]을 사용하여 하위 배열 arr[0,…,x]의 합계를 반환합니다.
1) 출력 합계를 0으로, 현재 인덱스를 x+1로 초기화합니다.
2) 현재 인덱스가 0보다 큰 동안 다음을 수행합니다.
...a) 합계에 BITree[index]를 추가합니다.
…b) BITree[index]의 상위로 이동합니다. 부모는 제거하여 얻을 수 있습니다
현재 인덱스의 마지막 세트 비트, 즉 index = index – (index & (-index))
3) 반환 금액.



비트섬

위의 다이어그램은 getSum()이 작동하는 방식의 예를 제공합니다. 다음은 몇 가지 중요한 관찰입니다.
BITree[0]은 더미 노드입니다.
BITree[y]는 BITree[x]의 상위입니다. 즉, x의 이진 표현에서 마지막 세트 비트를 제거하여 y를 얻을 수 있는 경우에만 해당됩니다. 즉, y = x – (x & (-x))입니다.
BITree[y] 노드의 하위 노드 BITree[x]는 y(포함)와 x(제외) 사이의 요소 합계(arr[y,…,x))를 저장합니다.

update(x, val): arr[index] += val을 수행하여 BIT(Binary Indexed Tree)를 업데이트합니다.
// update(x, val) 작업은 arr[]을 변경하지 않는다는 점에 유의하세요. BITree[]만 변경합니다.
1) 현재 인덱스를 x+1로 초기화합니다.
2) 현재 인덱스가 n보다 작거나 같을 때 다음을 수행합니다.
...a) BITree[index]에 val을 추가합니다.
…b) BITree[index]의 다음 요소로 이동합니다. 다음 요소는 현재 인덱스의 마지막 세트 비트를 증가시켜 얻을 수 있습니다. 즉, 인덱스 = 인덱스 + (인덱스 & (-인덱스))



비트업데이트1

업데이트 기능은 해당 범위 내에 arr[i]를 포함하는 모든 BITree 노드가 업데이트되는지 확인해야 합니다. 현재 인덱스의 마지막 설정된 비트에 해당하는 10진수를 반복적으로 추가하여 BITree에서 이러한 노드를 반복합니다.
이진 인덱스 트리는 어떻게 작동하나요?
이 아이디어는 모든 양의 정수가 2의 거듭제곱의 합으로 표현될 수 있다는 사실에 기초합니다. 예를 들어 19는 16 + 2 + 1로 표현될 수 있습니다. BITree의 모든 노드는 n 요소의 합을 저장합니다. 여기서 n은 예를 들어 위의 첫 번째 다이어그램(getSum()에 대한 다이어그램)에서 처음 12개 요소의 합은 마지막 4개 요소(9~12)의 합과 8의 합으로 얻을 수 있습니다. 요소(1~8). 숫자 n의 이진 표현에서 설정된 비트 수는 O(Logn)입니다. 따라서 getSum() 및 update() 작업 모두에서 최대 O(Logn) 노드를 순회합니다. 모든 n개 요소에 대해 update()를 호출하므로 구성의 시간 복잡도는 O(nLogn)입니다.
구현:
다음은 Binary Indexed Tree의 구현입니다.

C++




// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->입력 배열에 있는 요소 수입니다.> >BITree[0..n] -->이진 인덱스 트리를 나타내는 배열입니다.> >arr[0..n-1] -->접두사 합계가 평가되는 입력 배열입니다. */> > // Returns sum of arr[0..index]. This function assumes> // that the array is preprocessed and partial sums of> // array elements are stored in BITree[].> int> getSum(>int> BITree[],>int> index)> {> >int> sum = 0;>// Initialize result> > >// index in BITree[] is 1 more than the index in arr[]> >index = index + 1;> > >// Traverse ancestors of BITree[index]> >while> (index>0)> >{> >// Add current element of BITree to sum> >sum += BITree[index];> > >// Move index to parent node in getSum View> >index -= index & (-index);> >}> >return> sum;> }> > // Updates a node in Binary Index Tree (BITree) at given index> // in BITree. The given value 'val' is added to BITree[i] and> // all of its ancestors in tree.> void> updateBIT(>int> BITree[],>int> n,>int> index,>int> val)> {> >// index in BITree[] is 1 more than the index in arr[]> >index = index + 1;> > >// Traverse all ancestors and add 'val'> >while> (index <= n)> >{> >// Add 'val' to current node of BI Tree> >BITree[index] += val;> > >// Update index to that of parent in update View> >index += index & (-index);> >}> }> > // Constructs and returns a Binary Indexed Tree for given> // array of size n.> int> *constructBITree(>int> arr[],>int> n)> {> >// Create and initialize BITree[] as 0> >int> *BITree =>new> int>[n+1];> >for> (>int> i=1; i<=n; i++)> >BITree[i] = 0;> > >// Store the actual values in BITree[] using update()> >for> (>int> i=0; i updateBIT(BITree, n, i, arr[i]); // Uncomment below lines to see contents of BITree[] //for (int i=1; i<=n; i++) // cout << BITree[i] << ' '; return BITree; } // Driver program to test above functions int main() { int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; int n = sizeof(freq)/sizeof(freq[0]); int *BITree = constructBITree(freq, n); cout << 'Sum of elements in arr[0..5] is ' << getSum(BITree, 5); // Let use test the update operation freq[3] += 6; updateBIT(BITree, n, 3, 6); //Update BIT for above change in arr[] cout << ' Sum of elements in arr[0..5] after update is ' << getSum(BITree, 5); return 0; }>

>

>

자바




정렬된 배열 목록 자바

// Java program to demonstrate lazy> // propagation in segment tree> import> java.util.*;> import> java.lang.*;> import> java.io.*;> > class> BinaryIndexedTree> {> >// Max tree size> >final> static> int> MAX =>1000>;> > >static> int> BITree[] =>new> int>[MAX];> > >/* n -->입력 배열에 있는 요소 수입니다.> >BITree[0..n] -->바이너리를 나타내는 배열> >Indexed Tree.> >arr[0..n-1] -->접두어 합이>'>인 입력 배열 >// its ancestors in tree.> >public> static> void> updateBIT(>int> n,>int> index,> >int> val)> >{> >// index in BITree[] is 1 more than> >// the index in arr[]> >index = index +>1>;> > >// Traverse all ancestors and add 'val'> >while>(index <= n)> >{> >// Add 'val' to current node of BIT Tree> >BITree[index] += val;> > >// Update index to that of parent> >// in update View> >index += index & (-index);> >}> >}> > >/* Function to construct fenwick tree> >from given array.*/> >void> constructBITree(>int> arr[],>int> n)> >{> >// Initialize BITree[] as 0> >for>(>int> i=>1>; i<=n; i++)> >BITree[i] =>0>;> > >// Store the actual values in BITree[]> >// using update()> >for>(>int> i =>0>; i updateBIT(n, i, arr[i]); } // Main function public static void main(String args[]) { int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; int n = freq.length; BinaryIndexedTree tree = new BinaryIndexedTree(); // Build fenwick tree from given array tree.constructBITree(freq, n); System.out.println('Sum of elements in arr[0..5]'+ ' is '+ tree.getSum(5)); // Let use test the update operation freq[3] += 6; // Update BIT for above change in arr[] updateBIT(n, 3, 6); // Find sum after the value is updated System.out.println('Sum of elements in arr[0..5]'+ ' after update is ' + tree.getSum(5)); } } // This code is contributed by Ranjan Binwani>

>

>

파이썬3




# Python implementation of Binary Indexed Tree> > # Returns sum of arr[0..index]. This function assumes> # that the array is preprocessed and partial sums of> # array elements are stored in BITree[].> def> getsum(BITTree,i):> >s>=> 0> #initialize result> > ># index in BITree[] is 1 more than the index in arr[]> >i>=> i>+>1> > ># Traverse ancestors of BITree[index]> >while> i>>0>:> > ># Add current element of BITree to sum> >s>+>=> BITTree[i]> > ># Move index to parent node in getSum View> >i>->=> i & (>->i)> >return> s> > # Updates a node in Binary Index Tree (BITree) at given index> # in BITree. The given value 'val' is added to BITree[i] and> # all of its ancestors in tree.> def> updatebit(BITTree , n , i ,v):> > ># index in BITree[] is 1 more than the index in arr[]> >i>+>=> 1> > ># Traverse all ancestors and add 'val'> >while> i <>=> n:> > ># Add 'val' to current node of BI Tree> >BITTree[i]>+>=> v> > ># Update index to that of parent in update View> >i>+>=> i & (>->i)> > > # Constructs and returns a Binary Indexed Tree for given> # array of size n.> def> construct(arr, n):> > ># Create and initialize BITree[] as 0> >BITTree>=> [>0>]>*>(n>+>1>)> > ># Store the actual values in BITree[] using update()> >for> i>in> range>(n):> >updatebit(BITTree, n, i, arr[i])> > ># Uncomment below lines to see contents of BITree[]> >#for i in range(1,n+1):> ># print BITTree[i],> >return> BITTree> > > # Driver code to test above methods> freq>=> [>2>,>1>,>1>,>3>,>2>,>3>,>4>,>5>,>6>,>7>,>8>,>9>]> BITTree>=> construct(freq,>len>(freq))> print>(>'Sum of elements in arr[0..5] is '> +> str>(getsum(BITTree,>5>)))> freq[>3>]>+>=> 6> updatebit(BITTree,>len>(freq),>3>,>6>)> print>(>'Sum of elements in arr[0..5]'>+> >' after update is '> +> str>(getsum(BITTree,>5>)))> > # This code is contributed by Raju Varshney>

>

>

씨#




// C# program to demonstrate lazy> // propagation in segment tree> using> System;> > public> class> BinaryIndexedTree> {> >// Max tree size> >readonly> static> int> MAX = 1000;> > >static> int> []BITree =>new> int>[MAX];> > >/* n -->입력 배열에 있는 요소 수입니다.> >BITree[0..n] -->바이너리를 나타내는 배열> >Indexed Tree.> >arr[0..n-1] -->접두어 합이>'>인 입력 배열 >// its ancestors in tree.> >public> static> void> updateBIT(>int> n,>int> index,> >int> val)> >{> >// index in BITree[] is 1 more than> >// the index in arr[]> >index = index + 1;> > >// Traverse all ancestors and add 'val'> >while>(index <= n)> >{> > >// Add 'val' to current node of BIT Tree> >BITree[index] += val;> > >// Update index to that of parent> >// in update View> >index += index & (-index);> >}> >}> > >/* Function to construct fenwick tree> >from given array.*/> >void> constructBITree(>int> []arr,>int> n)> >{> >// Initialize BITree[] as 0> >for>(>int> i = 1; i <= n; i++)> >BITree[i] = 0;> > >// Store the actual values in BITree[]> >// using update()> >for>(>int> i = 0; i updateBIT(n, i, arr[i]); } // Driver code public static void Main(String []args) { int []freq = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; int n = freq.Length; BinaryIndexedTree tree = new BinaryIndexedTree(); // Build fenwick tree from given array tree.constructBITree(freq, n); Console.WriteLine('Sum of elements in arr[0..5]'+ ' is '+ tree.getSum(5)); // Let use test the update operation freq[3] += 6; // Update BIT for above change in arr[] updateBIT(n, 3, 6); // Find sum after the value is updated Console.WriteLine('Sum of elements in arr[0..5]'+ ' after update is ' + tree.getSum(5)); } } // This code is contributed by PrinciRaj1992>

>

>

자바스크립트




> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->입력 배열에 있는 요소 수입니다.> >BITree[0..n] -->바이너리를 나타내는 배열> >Indexed Tree.> >arr[0..n-1] -->접두어 합이>'>인 입력 배열 >// its ancestors in tree.> function> updateBIT(n,index,val)> {> >// index in BITree[] is 1 more than> >// the index in arr[]> >index = index + 1;> > >// Traverse all ancestors and add 'val'> >while>(index <= n)> >{> >// Add 'val' to current node of BIT Tree> >BITree[index] += val;> > >// Update index to that of parent> >// in update View> >index += index & (-index);> >}> }> > /* Function to construct fenwick tree> >from given array.*/> function> constructBITree(arr,n)> {> >// Initialize BITree[] as 0> >for>(let i=1; i<=n; i++)> >BITree[i] = 0;> > >// Store the actual values in BITree[]> >// using update()> >for>(let i = 0; i updateBIT(n, i, arr[i]); } // Main function let freq=[2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9]; let n = freq.length; // Build fenwick tree from given array constructBITree(freq, n); document.write('Sum of elements in arr[0..5]'+ ' is '+ getSum(5)+' '); // Let use test the update operation freq[3] += 6; // Update BIT for above change in arr[] updateBIT(n, 3, 6); // Find sum after the value is updated document.write('Sum of elements in arr[0..5]'+ ' after update is ' + getSum(5)); // This code is contributed by patel2127>

>

>

산출

Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>

시간 복잡도: O(NLogN)
보조 공간: 에)

이진 인덱스 트리를 O(Logn) 시간 내에 범위의 합을 계산하도록 확장할 수 있습니까?
예. rangeSum(l, r) = getSum(r) – getSum(l-1).
신청:
산술 코딩 알고리즘의 구현. Binary Indexed Tree의 개발은 주로 이 경우의 적용에 의해 동기가 부여되었습니다. 보다 이것 상세 사항은.
예제 문제:
배열의 반전 계산 | 세트 3(BIT 사용)
2차원 이진 인덱스 트리 또는 펜윅 트리
BIT를 사용하여 직사각형 공간에서 삼각형 세기

참고자료:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees