Låt oss överväga följande problem för att förstå Binary Indexed Tree.
Vi har en array arr[0 . . . n-1]. Vi skulle vilja
1 Beräkna summan av de första i-elementen.
2 Ändra värdet för ett specificerat element i arrayen arr[i] = x där 0 <= i <= n-1.
A enkel lösning är att köra en slinga från 0 till i-1 och beräkna summan av elementen. För att uppdatera ett värde, gör helt enkelt arr[i] = x. Den första operationen tar O(n) tid och den andra operationen tar O(1) tid. En annan enkel lösning är att skapa en extra array och lagra summan av de första i:te elementen vid det i:te indexet i denna nya array. Summan av ett givet intervall kan nu beräknas i O(1) tid, men uppdateringsoperationen tar nu O(n) tid. Detta fungerar bra om det finns ett stort antal frågeoperationer men ett väldigt få antal uppdateringsoperationer.
Skulle vi kunna utföra både fråge- och uppdateringsoperationerna i O(log n)-tid?
En effektiv lösning är att använda Segment Tree som utför båda operationerna i O(Logn)-tid.
En alternativ lösning är Binary Indexed Tree, som också uppnår O(Logn) tidskomplexitet för båda operationerna. Jämfört med Segment Tree kräver Binary Indexed Tree mindre utrymme och är lättare att implementera. .
Representation
Binärt indexerat träd representeras som en array. Låt arrayen vara BITree[]. Varje nod i det binära indexerade trädet lagrar summan av vissa element i inmatningsmatrisen. Storleken på det binära indexerade trädet är lika med storleken på inmatningsmatrisen, betecknad som n. I koden nedan använder vi storleken n+1 för att underlätta implementeringen.
Konstruktion
Vi initialiserar alla värden i BITree[] som 0. Sedan anropar vi update() för alla index, operationen update() diskuteras nedan.
Operationer
getSum(x): Returnerar summan av undermatrisen arr[0,...,x]
// Returnerar summan av undermatrisen arr[0,...,x] med hjälp av BITree[0..n], som är konstruerad från arr[0..n-1]
1) Initiera utgångssumman som 0, det aktuella indexet som x+1.
2) Gör följande medan det aktuella indexet är större än 0.
…a) Lägg till BITree[index] till summan
…b) Gå till föräldern till BITree[index]. Föräldern kan erhållas genom att ta bort
den sista inställda biten från det aktuella indexet, dvs index = index – (index & (-index))
3) Retursumma.
Diagrammet ovan ger ett exempel på hur getSum() fungerar. Här är några viktiga observationer.
BITree[0] är en dummynod.
BITree[y] är föräldern till BITree[x], om och endast om y kan erhållas genom att ta bort den sista inställda biten från den binära representationen av x, det vill säga y = x – (x & (-x)).
Den underordnade noden BITree[x] för noden BITree[y] lagrar summan av elementen mellan y(inklusive) och x(exklusiv): arr[y,...,x).
update(x, val): Uppdaterar det binära indexerade trädet (BIT) genom att utföra arr[index] += val
// Observera att update(x, val) operationen inte kommer att ändra arr[]. Den gör bara ändringar i BITree[]
1) Initiera det aktuella indexet som x+1.
2) Gör följande medan det aktuella indexet är mindre än eller lika med n.
…a) Lägg till värdet till BITree[index]
…b) Gå till nästa element i BITree[index]. Nästa element kan erhållas genom att öka den sista inställda biten i det aktuella indexet, dvs index = index + (index & (-index))
Uppdateringsfunktionen måste se till att alla BITree-noder som innehåller arr[i] inom sina intervall uppdateras. Vi loopar över sådana noder i BITree genom att upprepade gånger lägga till det decimaltal som motsvarar den sista inställda biten i det aktuella indexet.
Hur fungerar Binary Indexed Tree?
Idén bygger på det faktum att alla positiva heltal kan representeras som summan av potenser av 2. Till exempel kan 19 representeras som 16 + 2 + 1. Varje nod i BITree lagrar summan av n element där n är en Potensen 2. Till exempel, i det första diagrammet ovan (diagrammet för getSum()), kan summan av de första 12 elementen erhållas genom summan av de fyra sista elementen (från 9 till 12) plus summan av 8 element (från 1 till 8). Antalet setbitar i den binära representationen av ett tal n är O(Logn). Därför korsar vi som mest O(Logn)-noder i både getSum()- och update()-operationer. Konstruktionens tidskomplexitet är O(nLogn) eftersom den anropar update() för alla n element.
Genomförande:
Följande är implementeringarna av Binary Indexed Tree.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Antal element som finns i inmatningsmatrisen.> >BITree[0..n] -->Array som representerar binärt indexerat träd.> >arr[0..n-1] -->Inmatningsmatris för vilken prefixsumma utvärderas. */> > // 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
försök fånga 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 -->Antal element som finns i inmatningsmatrisen.> >BITree[0..n] -->Array som representerar binär> >Indexed Tree.> >arr[0..n-1] -->Inmatningsmatris för vilket prefix summa> >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#
// 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 -->Antal element som finns i inmatningsmatrisen.> >BITree[0..n] -->Array som representerar binär> >Indexed Tree.> >arr[0..n-1] -->Inmatningsmatris för vilket prefix summa> >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> |
>
>
Javascript
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Antal element som finns i inmatningsmatrisen.> >BITree[0..n] -->Array som representerar binär> >Indexed Tree.> >arr[0..n-1] -->Inmatningsmatris för vilket prefix summa> >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> |
>
>Produktion
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Tidskomplexitet: O(NLogN)
Hjälputrymme: PÅ)
Kan vi utöka det binära indexerade trädet till att beräkna summan av ett intervall i O(Logn)-tid?
Ja. rangeSum(l, r) = getSum(r) – getSum(l-1).
Applikationer:
Implementeringen av den aritmetiska kodningsalgoritmen. Utvecklingen av det binära indexerade trädet motiverades främst av dess tillämpning i detta fall. Ser detta för mer detaljer.
Exempel på problem:
Räkna inversioner i en array | Set 3 (med BIT)
Tvådimensionellt binärt indexerat träd eller Fenwick-träd
Räkna trianglar i ett rektangulärt utrymme med hjälp av BIT
Referenser:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees