Considérons le problème suivant pour comprendre l'arbre indexé binaire.
Nous avons un tableau arr[0 . . . n-1]. Nous voudrions
1 Calculez la somme des i premiers éléments.
2 Modifiez la valeur d'un élément spécifié du tableau arr[i] = x où 0 <= i <= n-1.
UN solution simple consiste à exécuter une boucle de 0 à i-1 et à calculer la somme des éléments. Pour mettre à jour une valeur, faites simplement arr[i] = x. La première opération prend un temps O(n) et la deuxième opération prend un temps O(1). Une autre solution simple consiste à créer un tableau supplémentaire et à stocker la somme des premiers éléments au i-ième index dans ce nouveau tableau. La somme d'une plage donnée peut désormais être calculée en temps O(1), mais l'opération de mise à jour prend désormais un temps O(n). Cela fonctionne bien s'il y a un grand nombre d'opérations de requête mais un très petit nombre d'opérations de mise à jour.
Pourrions-nous effectuer à la fois les opérations de requête et de mise à jour en un temps O(log n) ?
Une solution efficace consiste à utiliser Segment Tree qui effectue les deux opérations en un temps O(Logn).
Une solution alternative est l'arbre indexé binaire, qui atteint également une complexité temporelle O(Logn) pour les deux opérations. Par rapport à l’arborescence de segments, l’arborescence indexée binaire nécessite moins d’espace et est plus facile à mettre en œuvre. .
Représentation
L'arbre indexé binaire est représenté sous forme de tableau. Soit le tableau BITree[]. Chaque nœud de l'arbre indexé binaire stocke la somme de certains éléments du tableau d'entrée. La taille de l’arbre indexé binaire est égale à la taille du tableau d’entrée, notée n. Dans le code ci-dessous, nous utilisons une taille de n+1 pour faciliter la mise en œuvre.
Construction
Nous initialisons toutes les valeurs de BITree[] à 0. Ensuite, nous appelons update() pour tous les index, l'opération update() est décrite ci-dessous.
Opérations
getSum(x) : renvoie la somme du sous-tableau arr[0,…,x]
// Renvoie la somme du sous-tableau arr[0,…,x] en utilisant BITree[0..n], qui est construit à partir de arr[0..n-1]
1) Initialisez la somme de sortie à 0, l'index actuel à x+1.
2) Faites ce qui suit pendant que l'index actuel est supérieur à 0.
…a) Ajoutez BITree[index] à la somme
…b) Accédez au parent de BITree[index]. Le parent peut être obtenu en supprimant
le dernier bit défini à partir de l'index actuel, c'est-à-dire index = index – (index & (-index))
3) Renvoyez la somme.
Le diagramme ci-dessus fournit un exemple du fonctionnement de getSum(). Voici quelques observations importantes.
BITree[0] est un nœud factice.
BITree[y] est le parent de BITree[x], si et seulement si y peut être obtenu en supprimant le dernier bit défini de la représentation binaire de x, c'est-à-dire y = x – (x & (-x)).
Le nœud enfant BITree[x] du nœud BITree[y] stocke la somme des éléments entre y(inclus) et x(exclusif) : arr[y,…,x).
update(x, val) : met à jour l'arbre indexé binaire (BIT) en effectuant arr[index] += val
// Notez que l'opération update(x, val) ne changera pas arr[]. Il apporte uniquement des modifications à BITree[]
1) Initialisez l'index actuel comme x+1.
2) Effectuez ce qui suit pendant que l'index actuel est inférieur ou égal à n.
…a) Ajoutez le val à BITree[index]
…b) Accédez à l'élément suivant de BITree[index]. L'élément suivant peut être obtenu en incrémentant le dernier bit défini de l'index actuel, c'est-à-dire index = index + (index & (-index))
La fonction de mise à jour doit s'assurer que tous les nœuds BITree qui contiennent arr[i] dans leurs plages sont mis à jour. Nous parcourons ces nœuds dans le BITree en ajoutant à plusieurs reprises le nombre décimal correspondant au dernier bit défini de l'index actuel.
Comment fonctionne l’arbre indexé binaire ?
L'idée est basée sur le fait que tous les entiers positifs peuvent être représentés comme la somme des puissances de 2. Par exemple, 19 peut être représenté par 16 + 2 + 1. Chaque nœud du BITree stocke la somme de n éléments où n est un puissance de 2. Par exemple, dans le premier diagramme ci-dessus (le diagramme pour getSum()), la somme des 12 premiers éléments peut être obtenue par la somme des 4 derniers éléments (de 9 à 12) plus la somme de 8 éléments (de 1 à 8). Le nombre de bits définis dans la représentation binaire d'un nombre n est O(Logn). Par conséquent, nous parcourons au plus les nœuds O(Logn) dans les opérations getSum() et update(). La complexité temporelle de la construction est O(nLogn) car elle appelle update() pour les n éléments.
Mise en œuvre:
Voici les implémentations de l’arbre indexé binaire.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Nombre d'éléments présents dans le tableau d'entrée.> >BITree[0..n] -->Tableau qui représente l'arbre indexé binaire.> >arr[0..n-1] -->Tableau d’entrée pour lequel la somme des préfixes est évaluée. */> > // 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; }> |
lexicographiquement
>
>
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'éléments présents dans le tableau d'entrée.> >BITree[0..n] -->Tableau qui représente Binaire> >Indexed Tree.> >arr[0..n-1] -->Tableau d'entrée pour lequel la somme des préfixes> >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#
nfa en dfa
// 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'éléments présents dans le tableau d'entrée.> >BITree[0..n] -->Tableau qui représente Binaire> >Indexed Tree.> >arr[0..n-1] -->Tableau d'entrée pour lequel la somme des préfixes> >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> |
sont des exemples de modèles
>
>
Javascript
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Nombre d'éléments présents dans le tableau d'entrée.> >BITree[0..n] -->Tableau qui représente Binaire> >Indexed Tree.> >arr[0..n-1] -->Tableau d'entrée pour quelle somme de préfixe> >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> |
>
>Sortir
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Complexité temporelle : O(NLogN)
Espace auxiliaire : SUR)
Pouvons-nous étendre l'arbre indexé binaire au calcul de la somme d'une plage en temps O(Logn) ?
Oui. rangeSum(l, r) = getSum(r) – getSum(l-1).
Applications:
La mise en œuvre de l'algorithme de codage arithmétique. Le développement de l’arbre indexé binaire a été principalement motivé par son application dans ce cas. Voir ce pour plus de détails.
Exemples de problèmes :
Compter les inversions dans un tableau | Ensemble 3 (utilisation de BIT)
Arbre indexé binaire bidimensionnel ou arbre Fenwick
Compter les triangles dans un espace rectangulaire à l'aide de BIT
Les références:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees