이진 인덱스 트리를 이해하기 위해 다음 문제를 고려해 보겠습니다.
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]의 다음 요소로 이동합니다. 다음 요소는 현재 인덱스의 마지막 세트 비트를 증가시켜 얻을 수 있습니다. 즉, 인덱스 = 인덱스 + (인덱스 & (-인덱스))
업데이트 기능은 해당 범위 내에 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