La oss vurdere følgende problem for å forstå Binary Indexed Tree.
Vi har en matrise arr[0 . . . n-1]. Vi vil gjerne
1 Regn ut summen av de første i-elementene.
2 Endre verdien til et spesifisert element i matrisen arr[i] = x hvor 0 <= i <= n-1.
EN enkel løsning er å kjøre en sløyfe fra 0 til i-1 og beregne summen av elementene. For å oppdatere en verdi, gjør du ganske enkelt arr[i] = x. Den første operasjonen tar O(n) tid og den andre operasjonen tar O(1) tid. En annen enkel løsning er å lage en ekstra matrise og lagre summen av de første i-te elementene ved den i-te indeksen i denne nye matrisen. Summen av et gitt område kan nå beregnes i O(1) tid, men oppdateringsoperasjonen tar O(n) tid nå. Dette fungerer bra hvis det er et stort antall spørringsoperasjoner, men et svært få antall oppdateringsoperasjoner.
Kan vi utføre både spørringen og oppdateringsoperasjonene i O(log n)-tid?
En effektiv løsning er å bruke Segment Tree som utfører begge operasjonene i O(Logn) tid.
En alternativ løsning er Binary Indexed Tree, som også oppnår O(Logn)-tidskompleksitet for begge operasjonene. Sammenlignet med Segment Tree, krever Binary Indexed Tree mindre plass og er enklere å implementere. .
Representasjon
Binært indeksert tre er representert som en matrise. La matrisen være BITree[]. Hver node i det binære indekserte treet lagrer summen av noen elementer i inndatamatrisen. Størrelsen på det binære indekserte treet er lik størrelsen på inngangsmatrisen, betegnet som n. I koden nedenfor bruker vi en størrelse på n+1 for enkel implementering.
Konstruksjon
Vi initialiserer alle verdiene i BITree[] som 0. Deretter kaller vi update() for alle indeksene, update()-operasjonen er diskutert nedenfor.
Drift
getSum(x): Returnerer summen av undermatrisen arr[0,...,x]
// Returnerer summen av undermatrisen arr[0,...,x] ved å bruke BITree[0..n], som er konstruert fra arr[0..n-1]
1) Initialiser utgangssummen som 0, gjeldende indeks som x+1.
2) Følg med mens gjeldende indeks er større enn 0.
…a) Legg til BITree[indeks] til summen
…b) Gå til forelderen til BITree[indeks]. Forelderen kan fås ved å fjerne
den siste angitte biten fra gjeldende indeks, dvs. indeks = indeks – (indeks & (-indeks))
3) Retursum.
Diagrammet ovenfor gir et eksempel på hvordan getSum() fungerer. Her er noen viktige observasjoner.
BITree[0] er en dummy node.
BITree[y] er overordnet til BITree[x], hvis og bare hvis y kan oppnås ved å fjerne den siste angitte biten fra den binære representasjonen av x, det vil si y = x – (x & (-x)).
Undernoden BITree[x] til noden BITree[y] lagrer summen av elementene mellom y(inklusiv) og x(eksklusiv): arr[y,...,x).
update(x, val): Oppdaterer det binære indekserte treet (BIT) ved å utføre arr[index] += val
// Merk at update(x, val) operasjonen ikke vil endre arr[]. Den gjør bare endringer i BITree[]
1) Initialiser gjeldende indeks som x+1.
2) Gjør følgende mens gjeldende indeks er mindre enn eller lik n.
…a) Legg til verdien til BITree[indeks]
…b) Gå til neste element i BITree[indeks]. Det neste elementet kan oppnås ved å øke den siste innstilte biten av gjeldende indeks, dvs. indeks = indeks + (indeks & (-indeks))
Oppdateringsfunksjonen må sørge for at alle BITree-nodene som inneholder arr[i] innenfor sine områder blir oppdatert. Vi sløyfer over slike noder i BITree ved gjentatte ganger å legge til desimaltallet som tilsvarer den siste angitte biten i gjeldende indeks.
Hvordan fungerer binært indeksert tre?
Ideen er basert på det faktum at alle positive heltall kan representeres som summen av potenser av 2. For eksempel kan 19 representeres som 16 + 2 + 1. Hver node i BITree lagrer summen av n elementer der n er en potens av 2. For eksempel, i det første diagrammet ovenfor (diagrammet for getSum()), kan summen av de første 12 elementene oppnås ved summen av de siste 4 elementene (fra 9 til 12) pluss summen av 8 elementer (fra 1 til 8). Antall settbiter i den binære representasjonen av et tall n er O(Logn). Derfor krysser vi høyst O(Logn)-noder i både getSum()- og update()-operasjoner. Tidskompleksiteten til konstruksjonen er O(nLogn) som den kaller update() for alle n elementer.
Gjennomføring:
Følgende er implementeringene av Binary Indexed Tree.
C++
sortert arraylist i java
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Antall elementer som er tilstede i input-array.> >BITree[0..n] -->Array som representerer binært indeksert tre.> >arr[0..n-1] -->Inndatamatrise som prefikssum er evaluert 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
er kat timpf advokat
// 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 -->Antall elementer som er tilstede i input-array.> >BITree[0..n] -->Matrise som representerer Binær> >Indexed Tree.> >arr[0..n-1] -->Inndatamatrise for hvilket prefikssum> >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> |
>
>
hva er 10 av 1 million
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 -->Antall elementer som er tilstede i input-array.> >BITree[0..n] -->Matrise som representerer Binær> >Indexed Tree.> >arr[0..n-1] -->Inndatamatrise for hvilket prefikssum> >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
singleton design
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Antall elementer som er tilstede i input-array.> >BITree[0..n] -->Matrise som representerer Binær> >Indexed Tree.> >arr[0..n-1] -->Inndatamatrise for hvilket prefikssum> >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> |
>
>Produksjon
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Tidskompleksitet: O(NLogN)
Hjelpeplass: PÅ)
Kan vi utvide det binære indekserte treet til å beregne summen av et område i O(Logn)-tid?
Ja. rangeSum(l, r) = getSum(r) – getSum(l-1).
Applikasjoner:
Implementeringen av den aritmetiske kodingsalgoritmen. Utviklingen av det binære indekserte treet var først og fremst motivert av bruken i dette tilfellet. Se dette for flere detaljer.
Eksempler på problemer:
Tell inversjoner i en matrise | Sett 3 (bruker BIT)
Todimensjonalt binært indeksert tre eller Fenwick-tre
Å telle trekanter i et rektangulært rom ved å bruke BIT
Referanser:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees