Consideremos el siguiente problema para comprender el árbol indexado binario.
Tenemos una matriz arr[0 . . . n-1]. Nos gustaría
1 Calcula la suma de los primeros i elementos.
2 Modifique el valor de un elemento específico de la matriz arr[i] = x donde 0 <= i <= n-1.
A Solución simple es ejecutar un bucle de 0 a i-1 y calcular la suma de los elementos. Para actualizar un valor, simplemente haga arr[i] = x. La primera operación tarda O(n) tiempo y la segunda operación tarda O(1) tiempo. Otra solución simple es crear una matriz adicional y almacenar la suma de los primeros i-ésimos elementos en el índice i-ésimo de esta nueva matriz. La suma de un rango dado ahora se puede calcular en tiempo O(1), pero la operación de actualización ahora toma tiempo O(n). Esto funciona bien si hay una gran cantidad de operaciones de consulta pero muy pocas operaciones de actualización.
¿Podríamos realizar las operaciones de consulta y actualización en tiempo O (log n)?
Una solución eficaz es utilizar el árbol de segmentos que realiza ambas operaciones en tiempo O (Logn).
Una solución alternativa es el árbol indexado binario, que también logra una complejidad de tiempo O (Logn) para ambas operaciones. En comparación con el árbol de segmentos, el árbol indexado binario requiere menos espacio y es más fácil de implementar. .
Representación
El árbol indexado binario se representa como una matriz. Sea la matriz BITree[]. Cada nodo del árbol indexado binario almacena la suma de algunos elementos de la matriz de entrada. El tamaño del árbol indexado binario es igual al tamaño de la matriz de entrada, denotada como n. En el código siguiente, utilizamos un tamaño de n+1 para facilitar la implementación.
Construcción
Inicializamos todos los valores en BITree[] como 0. Luego llamamos a update() para todos los índices; la operación update() se analiza a continuación.
Operaciones
getSum(x): Devuelve la suma del subarreglo arr[0,…,x]
// Devuelve la suma del subarreglo arr[0,…,x] usando BITree[0..n], que se construye a partir de arr[0..n-1]
1) Inicialice la suma de salida como 0, el índice actual como x+1.
2) Haga lo siguiente mientras el índice actual sea mayor que 0.
…a) Sumar BITree[index] a la suma
…b) Ir al padre de BITree[index]. El padre se puede obtener eliminando
el último bit establecido del índice actual, es decir, índice = índice – (índice & (-índice))
3) Suma de devolución.subcadena de cadena java
El diagrama anterior proporciona un ejemplo de cómo funciona getSum(). He aquí algunas observaciones importantes.
BITree[0] es un nodo ficticio.
BITree[y] es el padre de BITree[x], si y sólo si y se puede obtener eliminando el último bit establecido de la representación binaria de x, es decir y = x – (x & (-x)).
El nodo hijo BITree[x] del nodo BITree[y] almacena la suma de los elementos entre y(inclusive) y x(exclusive): arr[y,…,x).
update(x, val): actualiza el árbol indexado binario (BIT) realizando arr[index] += val
// Tenga en cuenta que la operación update(x, val) no cambiará arr[]. Solo realiza cambios en BITree[]
1) Inicialice el índice actual como x+1.
2) Haga lo siguiente mientras el índice actual sea menor o igual a n.
…a) Agregue el valor a BITree[index]
…b) Ir al siguiente elemento de BITree[index]. El siguiente elemento se puede obtener incrementando el último bit establecido del índice actual, es decir, índice = índice + (índice & (-índice))
La función de actualización debe asegurarse de que se actualicen todos los nodos BITree que contienen arr[i] dentro de sus rangos. Recorremos dichos nodos en el BITree sumando repetidamente el número decimal correspondiente al último bit establecido del índice actual.
¿Cómo funciona el árbol indexado binario?
La idea se basa en el hecho de que todos los números enteros positivos se pueden representar como la suma de potencias de 2. Por ejemplo, 19 se puede representar como 16 + 2 + 1. Cada nodo del BITree almacena la suma de n elementos donde n es un potencia de 2. Por ejemplo, en el primer diagrama anterior (el diagrama de getSum()), la suma de los primeros 12 elementos se puede obtener mediante la suma de los últimos 4 elementos (del 9 al 12) más la suma de 8 elementos (del 1 al 8). El número de bits establecidos en la representación binaria de un número n es O (Logn). Por lo tanto, atravesamos como máximo los nodos O(Logn) en las operaciones getSum() y update(). La complejidad temporal de la construcción es O(nLogn), ya que llama a update() para los n elementos.
Implementación:
A continuación se muestran las implementaciones del árbol indexado binario.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Número de elementos presentes en la matriz de entrada.> >BITree[0..n] -->Matriz que representa el árbol indexado binario.> >arr[0..n-1] -->Matriz de entrada para la cual se evalúa la suma del prefijo. */> > // 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 -->Número de elementos presentes en la matriz de entrada.> >BITree[0..n] -->Matriz que representa Binario> >Indexed Tree.> >arr[0..n-1] -->Matriz de entrada para la cual suma de prefijo> >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 -->Número de elementos presentes en la matriz de entrada.> >BITree[0..n] -->Matriz que representa Binario> >Indexed Tree.> >arr[0..n-1] -->Matriz de entrada para la cual suma de prefijo> >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 -->Número de elementos presentes en la matriz de entrada.> >BITree[0..n] -->Matriz que representa Binario> >Indexed Tree.> >arr[0..n-1] -->Matriz de entrada para la cual suma de prefijo> >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> |
>
>
mapa en javaProducción
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Complejidad del tiempo: O(NLogN)
Espacio Auxiliar: EN)
¿Podemos extender el árbol indexado binario para calcular la suma de un rango en tiempo O (Logn)?
Sí. rangoSuma(l, r) = obtenerSuma(r) – obtenerSuma(l-1).
Aplicaciones:
La implementación del algoritmo de codificación aritmética. El desarrollo del árbol indexado binario estuvo motivado principalmente por su aplicación en este caso. Ver este para más detalles.
Problemas de ejemplo:
Contar inversiones en una matriz | Conjunto 3 (usando BIT)
Árbol indexado binario bidimensional o árbol Fenwick
Contar triángulos en un espacio rectangular usando BIT
Referencias:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees