Rozważmy następujący problem, aby zrozumieć drzewo indeksowane binarnie.
Mamy tablicę arr[0 . . . n-1]. Chcielibyśmy
1 Oblicz sumę pierwszych elementów i.
2 Zmodyfikuj wartość określonego elementu tablicy arr[i] = x gdzie 0 <= i <= n-1.
A proste rozwiązanie polega na uruchomieniu pętli od 0 do i-1 i obliczeniu sumy elementów. Aby zaktualizować wartość, po prostu wykonaj arr[i] = x. Pierwsza operacja zajmuje czas O(n), a druga operacja zajmuje czas O(1). Innym prostym rozwiązaniem jest utworzenie dodatkowej tablicy i zapisanie sumy pierwszych i-tych elementów pod i-tym indeksem tej nowej tablicy. Sumę danego zakresu można teraz obliczyć w czasie O(1), ale operacja aktualizacji zajmuje teraz czas O(n). Działa to dobrze, jeśli istnieje duża liczba operacji zapytań, ale bardzo mała liczba operacji aktualizacji.
Czy moglibyśmy wykonać zarówno operację zapytania, jak i aktualizację w czasie O(log n)?
Skutecznym rozwiązaniem jest użycie Segment Tree, które wykonuje obie operacje w czasie O(Logn).
Alternatywnym rozwiązaniem jest Binary Indexed Tree, które również osiąga złożoność czasową O(Logn) dla obu operacji. W porównaniu z drzewem segmentowym, drzewo indeksowane binarnie wymaga mniej miejsca i jest łatwiejsze do wdrożenia. .
Reprezentacja
Binarne drzewo indeksowane jest reprezentowane jako tablica. Niech tablicą będzie BITree[]. Każdy węzeł drzewa indeksowanego binarnie przechowuje sumę niektórych elementów tablicy wejściowej. Rozmiar drzewa indeksowanego binarnie jest równy rozmiarowi tablicy wejściowej, oznaczonej jako n. W poniższym kodzie używamy rozmiaru n+1 dla ułatwienia implementacji.
Budowa
Inicjujemy wszystkie wartości w BITree[] jako 0. Następnie wywołujemy funkcję update() dla wszystkich indeksów, operacja update() została omówiona poniżej.
Operacje
getSum(x): Zwraca sumę podtablicy arr[0,…,x]
// Zwraca sumę podtablicy arr[0,…,x] przy użyciu BITree[0..n], która jest zbudowana z arr[0..n-1]
1) Zainicjuj sumę wyjściową jako 0, bieżący indeks jako x+1.
2) Wykonaj następujące czynności, gdy bieżący indeks jest większy niż 0.
…a) Dodaj BITree[indeks] do sumy
…b) Przejdź do elementu nadrzędnego BITree[indeks]. Rodzica można uzyskać poprzez usunięcie
ostatni ustawiony bit z bieżącego indeksu, tj. indeks = indeks – (indeks & (-indeks))
3) Suma zwrotu.
Powyższy diagram przedstawia przykład działania metody getSum(). Oto kilka ważnych obserwacji.
BITree[0] to fikcyjny węzeł.
BITree[y] jest rodzicem BITree[x] wtedy i tylko wtedy, gdy y można uzyskać poprzez usunięcie ostatniego ustawionego bitu z binarnej reprezentacji x, czyli y = x – (x & (-x)).
Węzeł potomny BITree[x] węzła BITree[y] przechowuje sumę elementów pomiędzy y(włącznie) i x(wyłącznie): arr[y,…,x).
update(x, val): Aktualizuje drzewo indeksowane binarnie (BIT), wykonując arr[index] += val
// Zauważ, że operacja update(x, val) nie zmieni arr[]. Wprowadza zmiany tylko w BITree[]
1) Zainicjuj bieżący indeks jako x+1.
2) Wykonaj poniższe czynności, gdy bieżący indeks jest mniejszy lub równy n.
…a) Dodaj wartość do BITree[indeks]
…b) Przejdź do następnego elementu BITree[indeks]. Kolejny element można uzyskać zwiększając ostatni ustawiony bit bieżącego indeksu, czyli indeks = indeks + (indeks & (-indeks))
Funkcja aktualizacji musi upewnić się, że wszystkie węzły BITree zawierające arr[i] w swoich zakresach są aktualizowane. Zapętlamy takie węzły w BITree, wielokrotnie dodając liczbę dziesiętną odpowiadającą ostatniemu ustawionemu bitowi bieżącego indeksu.
Jak działa drzewo indeksowane binarnie?
Pomysł opiera się na fakcie, że wszystkie dodatnie liczby całkowite można przedstawić jako sumę potęg liczby 2. Na przykład 19 można przedstawić jako 16 + 2 + 1. Każdy węzeł BITree przechowuje sumę n elementów, gdzie n jest potęga liczby 2. Na przykład na pierwszym diagramie powyżej (schemat funkcji getSum()) sumę pierwszych 12 elementów można uzyskać poprzez sumę ostatnich 4 elementów (od 9 do 12) plus suma 8 elementy (od 1 do 8). Liczba ustawionych bitów w binarnej reprezentacji liczby n wynosi O(Logn). Dlatego w operacjach getSum() i update() przechodzimy co najwyżej O(Logn) węzłów. Złożoność czasowa konstrukcji wynosi O(nLogn), ponieważ wywołuje ona funkcję update() dla wszystkich n elementów.
Realizacja:
Poniżej znajdują się implementacje drzewa indeksowanego binarnie.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Liczba elementów obecnych w tablicy wejściowej.> >BITree[0..n] -->Tablica reprezentująca drzewo indeksowane binarnie.> >arr[0..n-1] -->Tablica wejściowa, dla której obliczana jest suma prefiksów. */> > // 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; }> |
podwójne w Javie
>
>
Jawa
// 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 -->Liczba elementów obecnych w tablicy wejściowej.> >BITree[0..n] -->Tablica reprezentująca Binary> >Indexed Tree.> >arr[0..n-1] -->Tablica wejściowa, dla której suma prefiksów> >is evaluated. */> > >// 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> 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.> >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> |
>
>
Python3
# 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#
prosty formater daty w Javie
// 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 -->Liczba elementów obecnych w tablicy wejściowej.> >BITree[0..n] -->Tablica reprezentująca Binary> >Indexed Tree.> >arr[0..n-1] -->Tablica wejściowa, dla której suma prefiksów> >is evaluated. */> > >// 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> 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.> >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> |
zmienna globalna JavaScript
>
>
JavaScript
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Liczba elementów obecnych w tablicy wejściowej.> >BITree[0..n] -->Tablica reprezentująca Binary> >Indexed Tree.> >arr[0..n-1] -->Tablica wejściowa, dla której suma prefiksów> >is evaluated. */> > >// Returns sum of arr[0..index]. This function> >// assumes that the array is preprocessed and> >// partial sums of array elements are stored> >// in BITree[].> function> getSum( index)> {> >let 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.> 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> |
>
>Wyjście
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Złożoność czasowa: O(NLogN)
Przestrzeń pomocnicza: NA)
Czy możemy rozszerzyć drzewo indeksowane binarnie do obliczania sumy zakresu w czasie O (logn)?
Tak. rangeSum(l, r) = getSum(r) – getSum(l-1).
Aplikacje:
Implementacja algorytmu kodowania arytmetycznego. Rozwój drzewa indeksowanego binarnie był motywowany przede wszystkim jego zastosowaniem w tym przypadku. Widzieć Ten po więcej szczegółów.
Przykładowe problemy:
Policz inwersje w tablicy | Zestaw 3 (przy użyciu BIT)
Dwuwymiarowe drzewo indeksowane binarnie lub drzewo Fenwicka
Liczenie trójkątów w przestrzeni prostokątnej za pomocą BIT-u
Bibliografia:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees