BINAIRE GEÏNDEXEERDE BOOM OF FENWICK TREE

Laten we het volgende probleem bekijken om de Binary Indexed Tree te begrijpen.
We hebben een array arr[0 . . . n-1]. Wij zouden graag willen
1 Bereken de som van de eerste i-elementen.
2 Wijzig de waarde van een gespecificeerd element van de array arr[i] = x waarbij 0 <= i <= n-1.
A eenvoudige oplossing is om een lus van 0 tot i-1 uit te voeren en de som van de elementen te berekenen. Om een waarde bij te werken, voert u eenvoudigweg arr[i] = x uit. De eerste bewerking kost O(n) tijd en de tweede bewerking kost O(1) tijd. Een andere eenvoudige oplossing is om een extra array te maken en de som van de eerste i-de elementen op te slaan bij de i-de index in deze nieuwe array. De som van een bepaald bereik kan nu in O(1) tijd worden berekend, maar de updatebewerking kost nu O(n) tijd. Dit werkt goed als er een groot aantal querybewerkingen is, maar een zeer klein aantal updatebewerkingen.
Kunnen we zowel de query- als de updatebewerkingen uitvoeren in O(log n)-tijd?
Een efficiënte oplossing is het gebruik van Segment Tree die beide bewerkingen in O(Logn)-tijd uitvoert.
Een alternatieve oplossing is Binary Indexed Tree, waarmee ook O(Logn)-tijdcomplexiteit voor beide bewerkingen wordt bereikt. Vergeleken met Segment Tree vereist Binary Indexed Tree minder ruimte en is gemakkelijker te implementeren. .
Vertegenwoordiging
Binary Indexed Tree wordt weergegeven als een array. Laat de array BITree[] zijn. Elk knooppunt van de binaire geïndexeerde boom slaat de som op van enkele elementen van de invoerarray. De grootte van de binaire geïndexeerde boom is gelijk aan de grootte van de invoerarray, aangegeven als n. In de onderstaande code gebruiken we de grootte n+1 voor een gemakkelijke implementatie.
Bouw
We initialiseren alle waarden in BITree[] als 0. Vervolgens roepen we update() aan voor alle indexen, de bewerking update() wordt hieronder besproken.
Activiteiten

getSum(x): Geeft de som terug van de subarray arr[0,…,x]
// Retourneert de som van de subarray arr[0,…,x] met behulp van BITree[0..n], die is opgebouwd uit arr[0..n-1]
1) Initialiseer de uitgangssom als 0, de huidige index als x+1.
2) Voer het volgende uit terwijl de huidige index groter is dan 0.
…a) Voeg BITree[index] toe aan de som
…b) Ga naar de ouder van BITree[index]. De ouder kan worden verkregen door te verwijderen
de laatst ingestelde bit van de huidige index, d.w.z. index = index – (index & (-index))
3) Retoursom.

BITSom

Het bovenstaande diagram geeft een voorbeeld van hoe getSum() werkt. Hier volgen enkele belangrijke observaties.
BITree[0] is een dummyknooppunt.
BITree[y] is de ouder van BITree[x], als en slechts als y kan worden verkregen door het laatste ingestelde bit uit de binaire representatie van x te verwijderen, dat wil zeggen y = x – (x & (-x)).
Het onderliggende knooppunt BITree[x] van het knooppunt BITree[y] slaat de som op van de elementen tussen y(inclusief) en x(exclusief): arr[y,…,x).

update(x, val): werkt de binaire geïndexeerde boom (BIT) bij door arr[index] += val uit te voeren
// Merk op dat de update(x, val) bewerking arr[] niet zal veranderen. Het brengt alleen wijzigingen aan in BITree[]
1) Initialiseer de huidige index als x+1.
2) Doe het volgende terwijl de huidige index kleiner is dan of gelijk is aan n.
…a) Voeg de val toe aan BITree[index]
…b) Ga naar het volgende element van BITree[index]. Het volgende element kan worden verkregen door het laatste ingestelde bit van de huidige index te verhogen, d.w.z. index = index + (index & (-index))

BITUpdate1

De updatefunctie moet ervoor zorgen dat alle BITree-knooppunten die arr[i] binnen hun bereik bevatten, worden bijgewerkt. We doorlopen dergelijke knooppunten in de BITree door herhaaldelijk het decimale getal toe te voegen dat overeenkomt met het laatst ingestelde bit van de huidige index.
Hoe werkt binaire geïndexeerde boom?
Het idee is gebaseerd op het feit dat alle positieve gehele getallen kunnen worden weergegeven als de som van machten van 2. 19 kan bijvoorbeeld worden weergegeven als 16 + 2 + 1. Elk knooppunt van de BITree slaat de som van n elementen op, waarbij n een macht van 2. In het eerste diagram hierboven (het diagram voor getSum()) kan de som van de eerste 12 elementen bijvoorbeeld worden verkregen door de som van de laatste 4 elementen (van 9 tot 12) plus de som van 8 elementen (van 1 tot 8). Het aantal ingestelde bits in de binaire representatie van een getal n is O(Logn). Daarom doorlopen we maximaal O(Logn)-knooppunten in zowel getSum()- als update()-bewerkingen. De tijdscomplexiteit van de constructie is O(nLogn), aangezien deze update() aanroept voor alle n elementen.
Implementatie:
Hieronder volgen de implementaties van Binary Indexed Tree.

C++

// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Aantal elementen aanwezig in invoerarray.> > BITree[0..n] -->Array die de binaire geïndexeerde boom vertegenwoordigt.> > arr[0..n-1] -->Invoerarray waarvoor de prefixsom wordt geëvalueerd. */> > // 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

// 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 -->Aantal elementen aanwezig in invoerarray.> > BITree[0..n] -->Array die Binair>'> vertegenwoordigt is > // 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#

// 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 -->Aantal elementen aanwezig in invoerarray.> > BITree[0..n] -->Array die Binair>'> vertegenwoordigt is > // 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

> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=> new> Array(MAX);> > /* n -->Aantal elementen aanwezig in invoerarray.> > BITree[0..n] -->Array die Binair>'> vertegenwoordigt is > // 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>

Uitvoer

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

Tijdcomplexiteit: O(NLogN)
Hulpruimte: OP)

Kunnen we de Binary Indexed Tree uitbreiden tot het berekenen van de som van een bereik in O(Logn)-tijd?
Ja. bereikSom(l, r) = getSum(r) – getSom(l-1).
Toepassingen:
De implementatie van het rekenkundige coderingsalgoritme. De ontwikkeling van de Binary Indexed Tree werd voornamelijk gemotiveerd door de toepassing ervan in dit geval. Zien dit voor meer details.
Voorbeeldproblemen:
Tel inversies in een array | Set 3 (met BIT)
Tweedimensionale binaire geïndexeerde boom of Fenwick-boom
Driehoeken tellen in een rechthoekige ruimte met BIT

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