Árbol indexado binario o árbol Fenwick

Posted on by Rudeus Greyrat

Consideremos el siguiente problema para comprender el árbol indexado binario.
Tenemos una array arr[0 . . . n-1]. Nos gustaría 
1 Calcular la suma de los primeros i elementos. 
2 Modificar el valor de un elemento especificado de la array arr[i] = x donde 0 <= i <= n-1.
Una solución sencillaes ejecutar un ciclo 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 toma el tiempo O(n) y la segunda operación toma el tiempo O(1). Otra solución simple es crear una array adicional y almacenar la suma de los primeros i-ésimos elementos en el i-ésimo índice de esta nueva array. 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 eficiente es usar Segment Tree que realiza ambas operaciones en tiempo O (Logn).
Una solución alternativa es Binary Indexed Tree, que también logra una complejidad de tiempo O(Logn) para ambas operaciones. Comparado con Segment Tree, Binary Indexed Tree requiere menos espacio y es más fácil de implementar. .
Representación 
El árbol indexado binario se representa como una array. Deje que la array sea BITree[]. Cada Node del árbol indexado binario almacena la suma de algunos elementos de la array de entrada. El tamaño del árbol indexado binario es igual al tamaño de la array de entrada, indicado como n. En el siguiente código, usamos 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 de actualización() 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 es construido 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) Agregue BITree[índice] a la suma 
…b) Vaya al padre de BITree[índice]. El padre se puede obtener eliminando 
el último bit establecido del índice actual, es decir, índice = índice – (índice & (-índice)) 
3) Devuelve la suma.

 

BITSuma

El diagrama anterior proporciona un ejemplo de cómo funciona getSum(). Aquí hay algunas observaciones importantes.
BITree[0] es un Node ficticio. 
BITree[y] es el padre de BITree[x], si y solo si y puede obtenerse eliminando el último bit establecido de la representación binaria de x, es decir y = x – (x & (-x)).
El Node hijo BITree[x] del Node BITree[y] almacena la suma de los elementos entre y(inclusive) yx(exclusive): arr[y,…,x). 
 

update(x, val): actualiza el árbol indexado binario (BIT) ejecutando arr[index] += val 
// Tenga en cuenta que la operación update(x, val) no cambiará arr[]. Solo realiza cambios en BITree[] 
1) Inicializa el índice actual como x+1. 
2) Haga lo siguiente mientras el índice actual sea menor o igual que n. 
…a) Agregue el valor a BITree[índice] 
…b) Vaya al siguiente elemento de BITree[índice]. El siguiente elemento se puede obtener incrementando el último bit establecido del índice actual, es decir, índice = índice + (índice & (-índice))

 

BITActualizar1

La función de actualización debe asegurarse de que se actualicen todos los Nodes BITree que contienen arr[i] dentro de sus rangos. Recorremos dichos Nodes en el BITree agregando 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 Node 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 (de 9 a 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 Nodes O(Logn) en las operaciones getSum() y update(). La complejidad temporal de la construcción es O(nLogn) ya que llama a update() para todos los n elementos. 
Implementación: 
Las siguientes son las implementaciones de Binary Indexed Tree.
 

C++

// C++ code to demonstrate operations of Binary Index Tree
#include <iostream>
  
using namespace std;
  
/*         n --> No. of elements present in input array. 
    BITree[0..n] --> Array that represents Binary Indexed Tree.
    arr[0..n-1] --> Input array for which prefix 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 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<n; 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 << "\nSum 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 --> No. of elements present in input array. 
    BITree[0..n] --> Array that represents Binary 
                    Indexed Tree.
    arr[0..n-1] --> Input array for which prefix 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 < n; 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 --> No. of elements present in input array. 
    BITree[0..n] --> Array that represents Binary 
                    Indexed Tree. 
    arr[0..n-1] --> Input array for which prefix 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 < n; 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

<script>
// Javascript program to demonstrate lazy
// propagation in segment tree
  
// Max tree size
let MAX = 1000;   
let BITree=new Array(MAX);
  
/* n --> No. of elements present in input array.
    BITree[0..n] --> Array that represents Binary
                    Indexed Tree.
    arr[0..n-1] --> Input array for which prefix 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 < n; 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)+"<br>");
  
// 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
</script>

Producción: 
 

Sum of elements in arr[0..5] is 12
Sum of elements in arr[0..5] after update is 18

¿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 fue motivado principalmente por su aplicación en este caso. Vea esto para más detalles.
Problemas de ejemplo:  
contar inversiones en una array | Conjunto 3 (Usando BIT)  
Árbol indexado binario bidimensional o  
Triángulos de conteo de árboles Fenwick 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
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *