Betrachten wir das folgende Problem, um den binär indizierten Baum zu verstehen.
Wir haben ein Array arr[0 . . . n-1]. Wir möchten
1 Berechnen Sie die Summe der ersten i Elemente.
2 Ändern Sie den Wert eines angegebenen Elements des Arrays arr[i] = x, wobei 0 <= i <= n-1.
A einfache Lösung besteht darin, eine Schleife von 0 bis i-1 auszuführen und die Summe der Elemente zu berechnen. Um einen Wert zu aktualisieren, führen Sie einfach arr[i] = x aus. Die erste Operation benötigt O(n) Zeit und die zweite Operation benötigt O(1) Zeit. Eine andere einfache Lösung besteht darin, ein zusätzliches Array zu erstellen und die Summe der ersten i-ten Elemente am i-ten Index in diesem neuen Array zu speichern. Die Summe eines bestimmten Bereichs kann jetzt in O(1) Zeit berechnet werden, aber der Aktualisierungsvorgang benötigt jetzt O(n) Zeit. Dies funktioniert gut, wenn viele Abfragevorgänge, aber nur sehr wenige Aktualisierungsvorgänge vorhanden sind.
Könnten wir sowohl die Abfrage- als auch die Aktualisierungsvorgänge in O(log n)-Zeit ausführen?
Eine effiziente Lösung besteht darin, einen Segmentbaum zu verwenden, der beide Operationen in O(Logn)-Zeit ausführt.
Eine alternative Lösung ist Binary Indexed Tree, die ebenfalls eine O(Logn)-Zeitkomplexität für beide Operationen erreicht. Im Vergleich zum Segmentbaum benötigt der binäre indizierte Baum weniger Platz und ist einfacher zu implementieren. .
Darstellung
Der binär indizierte Baum wird als Array dargestellt. Das Array sei BITree[]. Jeder Knoten des binär indizierten Baums speichert die Summe einiger Elemente des Eingabearrays. Die Größe des binär indizierten Baums entspricht der Größe des Eingabearrays, bezeichnet als n. Im folgenden Code verwenden wir zur einfacheren Implementierung eine Größe von n+1.
Konstruktion
Wir initialisieren alle Werte in BITree[] als 0. Dann rufen wir update() für alle Indizes auf, die update()-Operation wird weiter unten besprochen.
Operationen
getSum(x): Gibt die Summe des Unterarrays arr[0,…,x] zurück
// Gibt die Summe des Unterarrays arr[0,…,x] mit BITree[0..n] zurück, das aus arr[0..n-1] erstellt wird.
1) Initialisieren Sie die Ausgabesumme als 0, den aktuellen Index als x+1.
2) Führen Sie Folgendes aus, während der aktuelle Index größer als 0 ist.
…a) BITree[index] zur Summe hinzufügen
…b) Gehen Sie zum übergeordneten Element von BITree[index]. Das übergeordnete Element kann durch Entfernen erhalten werden
das zuletzt gesetzte Bit aus dem aktuellen Index, d. h. Index = Index – (Index & (-index))
3) Rückgabesumme.
Das obige Diagramm zeigt ein Beispiel für die Funktionsweise von getSum(). Hier sind einige wichtige Beobachtungen.
BITree[0] ist ein Dummy-Knoten.
BITree[y] ist genau dann das übergeordnete Element von BITree[x], wenn y durch Entfernen des letzten gesetzten Bits aus der binären Darstellung von x erhalten werden kann, d. h. y = x – (x & (-x)).
Der untergeordnete Knoten BITree[x] des Knotens BITree[y] speichert die Summe der Elemente zwischen y (einschließlich) und x (exklusiv): arr[y,…,x).
string.replaceall Java
update(x, val): Aktualisiert den Binary Indexed Tree (BIT) durch Ausführen von arr[index] += val
// Beachten Sie, dass die Operation update(x, val) arr[] nicht ändert. Es werden nur Änderungen an BITree[] vorgenommen.
1) Initialisieren Sie den aktuellen Index als x+1.
2) Führen Sie Folgendes aus, während der aktuelle Index kleiner oder gleich n ist.
…a) Den Wert zu BITree[index] hinzufügen
…b) Gehe zum nächsten Element von BITree[index]. Das nächste Element kann durch Inkrementieren des zuletzt gesetzten Bits des aktuellen Index erhalten werden, d. h. Index = Index + (Index & (-Index))
Die Aktualisierungsfunktion muss sicherstellen, dass alle BITree-Knoten, die arr[i] in ihren Bereichen enthalten, aktualisiert werden. Wir durchlaufen solche Knoten im BITree, indem wir wiederholt die Dezimalzahl addieren, die dem zuletzt gesetzten Bit des aktuellen Index entspricht.
Wie funktioniert der binär indizierte Baum?
Die Idee basiert auf der Tatsache, dass alle positiven ganzen Zahlen als Summe von Potenzen von 2 dargestellt werden können. Beispielsweise kann 19 als 16 + 2 + 1 dargestellt werden. Jeder Knoten des BITree speichert die Summe von n Elementen, wobei n a ist Potenz von 2. Beispielsweise kann im ersten Diagramm oben (dem Diagramm für getSum()) die Summe der ersten 12 Elemente durch die Summe der letzten 4 Elemente (von 9 bis 12) plus der Summe von 8 erhalten werden Elemente (von 1 bis 8). Die Anzahl der gesetzten Bits in der binären Darstellung einer Zahl n ist O(Logn). Daher durchlaufen wir in den Operationen getSum() und update() höchstens O(Logn)-Knoten. Die zeitliche Komplexität der Konstruktion beträgt O(nLogn), da update() für alle n Elemente aufgerufen wird.
Implementierung:
Im Folgenden sind die Implementierungen von Binary Indexed Tree aufgeführt.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Anzahl der im Eingabearray vorhandenen Elemente.> >BITree[0..n] -->Array, das den binär indizierten Baum darstellt.> >arr[0..n-1] -->Eingabearray, für das die Präfixsumme ausgewertet wird. */> > // 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; }> |
>
>
Wert der Java-Zeichenfolge
Java
// 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 -->Anzahl der im Eingabearray vorhandenen Elemente.> >BITree[0..n] -->Array, das Binär>'> darstellt >arr[0..n-1] -->Eingabearray, für das die Präfixsumme>'> gilt > >// 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> |
>
binäre Suche
>
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#
// 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 -->Anzahl der im Eingabearray vorhandenen Elemente.> >BITree[0..n] -->Array, das Binär>'> darstellt >arr[0..n-1] -->Eingabearray, für das die Präfixsumme>'> gilt > >// 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> |
>
Selen lernen
>
Javascript
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Anzahl der im Eingabearray vorhandenen Elemente.> >BITree[0..n] -->Array, das Binär>'> darstellt >arr[0..n-1] -->Eingabearray, für das die Präfixsumme>'> gilt > >// 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> |
>
>Ausgabe
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Zeitkomplexität: O(NLogN)
Hilfsraum: AN)
SQL mit zufälliger Reihenfolge
Können wir den binär indizierten Baum erweitern, um die Summe eines Bereichs in O(Logn)-Zeit zu berechnen?
Ja. rangeSum(l, r) = getSum(r) – getSum(l-1).
Anwendungen:
Die Implementierung des arithmetischen Codierungsalgorithmus. Die Entwicklung des Binary Indexed Tree wurde in erster Linie durch seine Anwendung in diesem Fall motiviert. Sehen Das für mehr Details.
Beispielprobleme:
Inversionen in einem Array zählen | Set 3 (mit BIT)
Zweidimensionaler binärer indizierter Baum oder Fenwick-Baum
Zählen von Dreiecken in einem rechteckigen Raum mit BIT
Verweise:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees