Lad os overveje følgende problem for at forstå Binary Indexed Tree.
Vi har en matrix arr[0 . . . n-1]. Vi vil gerne
1 Beregn summen af de første i-elementer.
2 Rediger værdien af et specificeret element i arrayet arr[i] = x hvor 0 <= i <= n-1.
EN enkel løsning er at køre en sløjfe fra 0 til i-1 og beregne summen af elementerne. For at opdatere en værdi skal du blot gøre arr[i] = x. Den første operation tager O(n) tid, og den anden operation tager O(1) tid. En anden simpel løsning er at oprette et ekstra array og gemme summen af de første i-te elementer ved det i-te indeks i dette nye array. Summen af et givet område kan nu beregnes i O(1) tid, men opdateringsoperationen tager nu O(n) tid. Dette fungerer godt, hvis der er et stort antal forespørgselsoperationer, men et meget få antal opdateringshandlinger.
Kunne vi udføre både forespørgslen og opdateringsoperationerne i O(log n) tid?
En effektiv løsning er at bruge Segment Tree, der udfører begge operationer i O(Logn) tid.
En alternativ løsning er Binary Indexed Tree, som også opnår O(Logn) tidskompleksitet for begge operationer. Sammenlignet med Segment Tree kræver Binary Indexed Tree mindre plads og er lettere at implementere. .
Repræsentation
Binært indekseret træ er repræsenteret som en matrix. Lad arrayet være BITree[]. Hver knude i det binære indekserede træ gemmer summen af nogle elementer i input-arrayet. Størrelsen af det binære indekserede træ er lig med størrelsen af input-arrayet, angivet som n. I koden nedenfor bruger vi en størrelse på n+1 for at lette implementeringen.
Konstruktion
Vi initialiserer alle værdierne i BITree[] som 0. Derefter kalder vi update() for alle indekserne, update() operationen er diskuteret nedenfor.
Operationer
getSum(x): Returnerer summen af underarrayet arr[0,...,x]
// Returnerer summen af underarrayet arr[0,…,x] ved hjælp af BITree[0..n], som er konstrueret ud fra arr[0..n-1]
1) Initialiser outputsummen som 0, det aktuelle indeks som x+1.
2) Følg med, mens det aktuelle indeks er større end 0.
…a) Tilføj BITree[indeks] til summen
…b) Gå til forælderen til BITree[indeks]. Forælderen kan fås ved at fjerne
den sidste indstillede bit fra det aktuelle indeks, dvs. indeks = indeks – (indeks & (-indeks))
3) Retursum.
Diagrammet ovenfor giver et eksempel på, hvordan getSum() fungerer. Her er nogle vigtige observationer.
BITree[0] er en dummy node.
BITree[y] er forælderen til BITree[x], hvis og kun hvis y kan opnås ved at fjerne den sidste sæt bit fra den binære repræsentation af x, det vil sige y = x – (x & (-x)).
Den underordnede node BITree[x] af noden BITree[y] gemmer summen af elementerne mellem y(inklusiv) og x(eksklusiv): arr[y,...,x).
update(x, val): Opdaterer det binære indekserede træ (BIT) ved at udføre arr[index] += val
// Bemærk, at update(x, val) operationen ikke ændrer arr[]. Den foretager kun ændringer i BITree[]
1) Initialiser det aktuelle indeks som x+1.
2) Gør følgende, mens det aktuelle indeks er mindre end eller lig med n.
…a) Tilføj værdien til BITree[indeks]
…b) Gå til næste element i BITree[indeks]. Det næste element kan opnås ved at øge den sidste indstillede bit af det aktuelle indeks, dvs. indeks = indeks + (indeks & (-indeks))
Opdateringsfunktionen skal sikre, at alle BITree-noder, som indeholder arr[i] inden for deres områder, opdateres. Vi sløjfer over sådanne noder i BITree ved gentagne gange at tilføje det decimaltal, der svarer til den sidste indstillede bit af det aktuelle indeks.
Hvordan virker binært indekseret træ?
Ideen er baseret på det faktum, at alle positive heltal kan repræsenteres som summen af potenser af 2. For eksempel kan 19 repræsenteres som 16 + 2 + 1. Hver knude i BITree gemmer summen af n elementer, hvor n er en potens af 2. For eksempel, i det første diagram ovenfor (diagrammet for getSum()), kan summen af de første 12 elementer fås ved summen af de sidste 4 elementer (fra 9 til 12) plus summen af 8 elementer (fra 1 til 8). Antallet af sæt bits i den binære repræsentation af et tal n er O(Logn). Derfor krydser vi højst O(Logn) noder i både getSum() og update() operationer. Konstruktionens tidskompleksitet er O(nLogn), da den kalder update() for alle n elementer.
Implementering:
Følgende er implementeringerne af Binary Indexed Tree.
C++
sorteret arraylist i java
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Antal elementer til stede i input-array.> >BITree[0..n] -->Array, der repræsenterer binært indekseret træ.> >arr[0..n-1] -->Input-array, som præfikssum evalueres for. */> > // 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
hvordan man får æble-emojis på Android
// 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 elementer til stede i input-array.> >BITree[0..n] -->Array, der repræsenterer Binær> >Indexed Tree.> >arr[0..n-1] -->Input array for hvilket præfiks sum> >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> |
>
>
string.valueof
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 elementer til stede i input-array.> >BITree[0..n] -->Array, der repræsenterer Binær> >Indexed Tree.> >arr[0..n-1] -->Input array for hvilket præfiks sum> >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
bellford algoritme
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Antal elementer til stede i input-array.> >BITree[0..n] -->Array, der repræsenterer Binær> >Indexed Tree.> >arr[0..n-1] -->Input array for hvilket præfiks sum> >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>
Tidskompleksitet: O(NLogN)
Hjælpeplads: PÅ)
Kan vi udvide det binære indekserede træ til at beregne summen af et interval i O(Logn) tid?
Ja. rangeSum(l, r) = getSum(r) – getSum(l-1).
Ansøgninger:
Implementeringen af den aritmetiske kodningsalgoritme. Udviklingen af det binære indekserede træ var primært motiveret af dets anvendelse i dette tilfælde. Se det her for flere detaljer.
Eksempler på problemer:
Tæl inversioner i et array | Sæt 3 (bruger BIT)
Todimensionelt binært indekseret træ eller Fenwick-træ
At tælle trekanter i et rektangulært rum ved hjælp af BIT
Referencer:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees