Considerem el següent problema per entendre l'arbre indexat binari.
Tenim una matriu arr[0 . . . n-1]. Ens agradaria
1 Calcula la suma dels primers i elements.
2 Modifiqueu el valor d'un element especificat de la matriu arr[i] = x on 0 <= i <= n-1.
A solució senzilla és executar un bucle de 0 a i-1 i calcular la suma dels elements. Per actualitzar un valor, simplement feu arr[i] = x. La primera operació triga O(n) temps i la segona operació triga O(1). Una altra solució senzilla és crear una matriu addicional i emmagatzemar la suma dels primers elements i-è a l'índex i-è d'aquesta nova matriu. La suma d'un rang determinat ara es pot calcular en temps O(1), però l'operació d'actualització triga ara O(n) temps. Això funciona bé si hi ha un gran nombre d'operacions de consulta però un nombre molt poc d'operacions d'actualització.
Podríem realitzar tant les operacions de consulta com d'actualització en temps O(log n)?
Una solució eficient és utilitzar l'arbre de segments que realitza les dues operacions en temps O(Logn).
Una solució alternativa és Binary Indexed Tree, que també aconsegueix la complexitat del temps O(Logn) per a ambdues operacions. En comparació amb l'arbre de segments, l'arbre indexat binari requereix menys espai i és més fàcil d'implementar. .
Representació
L'arbre indexat binari es representa com una matriu. Deixeu que la matriu sigui BITree[]. Cada node de l'arbre indexat binari emmagatzema la suma d'alguns elements de la matriu d'entrada. La mida de l'arbre indexat binari és igual a la mida de la matriu d'entrada, denotada com n. Al codi següent, utilitzem una mida de n+1 per facilitar la implementació.
Construcció
Inicialitzem tots els valors de BITree[] com a 0. Aleshores cridem a update() per a tots els índexs, l'operació update() s'explica a continuació.
Operacions
getSum(x): retorna la suma de la submatriu arr[0,...,x]
// Retorna la suma de la submatriu arr[0,...,x] utilitzant BITree[0..n], que es construeix a partir de arr[0..n-1]
1) Inicialitzar la suma de sortida com a 0, l'índex actual com a x+1.
2) Feu el seguiment mentre l'índex actual sigui superior a 0.
…a) Afegiu BITree[índex] a la suma
…b) Aneu al pare de BITree[índex]. El pare es pot obtenir eliminant
l'últim bit establert de l'índex actual, és a dir, índex = índex - (índex i (-índex))
3) Retorn de la suma.
El diagrama anterior proporciona un exemple de com funciona getSum(). Aquí hi ha algunes observacions importants.
BITree[0] és un node fictici.
BITree[y] és el pare de BITree[x], si i només si es pot obtenir y eliminant l'últim bit establert de la representació binària de x, és a dir, y = x – (x & (-x)).
El node fill BITree[x] del node BITree[y] emmagatzema la suma dels elements entre y(inclòs) i x(exclusiu): arr[y,...,x).
update(x, val): Actualitza l'arbre indexat binari (BIT) fent arr[índex] += val
// Tingueu en compte que l'operació d'actualització (x, val) no canviarà arr[]. Només fa canvis a BITree[]
1) Inicialitzar l'índex actual com a x+1.
2) Fes el següent mentre l'índex actual és menor o igual que n.
…a) Afegiu el valor a BITree[índex]
…b) Aneu al següent element de BITree[índex]. El següent element es pot obtenir incrementant l'últim bit establert de l'índex actual, és a dir, índex = índex + (índex i (-índex))
La funció d'actualització ha d'assegurar-se que s'actualitzen tots els nodes BITree que contenen arr[i] dins dels seus rangs. Fem un bucle sobre aquests nodes al BITree afegint repetidament el número decimal corresponent a l'últim bit establert de l'índex actual.
Com funciona l'arbre indexat binari?
La idea es basa en el fet que tots els nombres enters positius es poden representar com la suma de potències de 2. Per exemple, 19 es pot representar com 16 + 2 + 1. Cada node del BITree emmagatzema la suma de n elements on n és un potència de 2. Per exemple, al primer diagrama anterior (el diagrama de getSum()), la suma dels primers 12 elements es pot obtenir per la suma dels últims 4 elements (del 9 al 12) més la suma de 8 elements (de l'1 al 8). El nombre de bits establerts en la representació binària d'un nombre n és O(Logn). Per tant, travessem com a màxim nodes O(Logn) tant a les operacions getSum() com a update(). La complexitat temporal de la construcció és O(nLogn) ja que crida a update() per a tots els n elements.
Implementació:
A continuació es mostren les implementacions de Binary Indexed Tree.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Nombre d'elements presents a la matriu d'entrada.>>> > // 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 -->Nombre d'elements presents a la matriu d'entrada.>>> >arr[0..n-1] -->Matriu d'entrada per a quin prefix suma> >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> |
>
>
javascript
Python 3
# 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 -->Nombre d'elements presents a la matriu d'entrada.>>> >arr[0..n-1] -->Matriu d'entrada per a quin prefix suma> >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
el patrimoni net de kat timpf
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Nombre d'elements presents a la matriu d'entrada.>>> >arr[0..n-1] -->Matriu d'entrada per a quin prefix suma> >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> |
>
>Sortida
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Complexitat temporal: O(NLogN)
Espai auxiliar: O(N)
Podem estendre l'arbre indexat binari per calcular la suma d'un rang en temps O(Logn)?
Sí. rangeSum(l, r) = getSum(r) – getSum(l-1).
Aplicacions:
La implementació de l'algorisme de codificació aritmètica. El desenvolupament de l'arbre indexat binari va ser motivat principalment per la seva aplicació en aquest cas. Vegeu això per a més detalls.
Exemples de problemes:
Comptar les inversions en una matriu | Set 3 (utilitzant BIT)
Arbre bidimensional indexat bidimensional o arbre Fenwick
Comptar triangles en un espai rectangular amb BIT
Referències:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees