Árbol de Fenwick

El Árbol de Fenwick (también conocido como Árbol Binario Indexado o BIT por sus siglas en ingles) fue propuesto por Peter M Fenwick en 1994 para resolver problemas de compresión de datos. Es una estructura de datos muy eficiente para calcular sumas acumulativas. Para ilustrar el concepto de esta estructura, vamos a definir el siguiente problema:

Disponemos de n alcancias y varias monedas de distintos valores. Podemos insertar una moneda con cualquier valor en cualquiera de las alcancias, y estamos interesados en calcular la cantidad total de dinero que tenemos acumulada desde la alcancia 1 hasta la alcancia i.

bit_problem

Una forma de resolver este problema seria recorriendo cada alcancia desde 1 hasta i y sumar todos los valores para obtener la suma total, pero esta solucion es muy lenta cuando tenemos muchas alcancias. El BIT permite solucionar este problema de forma mas eficiente. Para solucionarlo, definiremos un arbol donde habran nodos responsables, y nodos dependientes.

Cada nodo responsable se encarga de mantener la suma de los valores de todos sus nodos dependientes. De esta manera, para calcular una suma en cualquier intervalo solo hay que tomar los valores en los nodos responsables que estén en el intervalo, y sumarlos, ya que estos comprimen en ellos la información de sus nodos dependientes.

Como determinar si un nodo es responsable o dependiente? Para esto definimos la función lowbit(i), la cual nos dice dado un numero i cual es el menor bit que tiene valor 1 en la representación binaria de este numero. Por ejemplo, el numero 6 es 110 en binario (1×2^2 + 1×2^1 + 0×2^0), y su menor bit es 1×2^1 = 2. Esto se puede calcular de la siguiente forma:

1
public int lowbit(int i) { return (i & -i); }

Este árbol puede ser representado implícitamente  asumiendo cada elemento original como un nodo en el árbol. Cada elemento i sera responsable por los elementos entre las posiciones i-lowbit(i)+1 hasta i, y almacenara el valor de la suma de los elementos en ese intervalo. Por ejemplo, lowbit(6)=2, por tanto, el elemento en la posición 6 es responsable por el elemento 5 y 6, y en el problema original, el valor seria la suma de la alcancia 5 + la suma de la alcancia 6. En el caso de 8, lowbit(8) = 8, y el elemento 8 seria responsable por los valores de las alcancias desde 1 hasta la 8.

Supongamos que los valores de las alcancías de la 1 hasta la 8 son [2, 3, 1, 1, 5, 6, 0, 1], respectivamente. En la siguiente figura podemos ver los elementos responsables y dependientes, y sus valores:

Árbol de Fenwick construido a partir de los valores

Obtener la suma acumulada

Dada una posición i, podemos usar el árbol de Fewick para obtener la suma de los valores acumulados desde la alcancía 1 hasta la alcancía i-esima. Esto es A[1] + A[2] + … + A[i]. La forma de hacer esto es comenzar en la posición i, y tomar los valores de los elementos responsables del árbol hasta llegar a 1.

NOTA: El árbol de Fenwick siempre comienza en la posición 1.

1
2
3
4
5
6
public int sum(int i)
{
    int value = 0;
    for(; i > 0; i-= lowbit(i)) value+= T[i];
    return value;
}

De forma similar, es posible que necesitemos la suma de los valores acumulados de la alcancia i hasta la j (i < j). Esto es A[i] + A[i+1] + … + A[j]. Esto lo podemos calcular haciendo sum(j) – sum(i-1), ya que el resultado de esto seria:

A[1] + A[2] + … + A[i-1] + A[i] + A[i+1] + … + A[j] – (A[1] + A[2] + … + A[i-1]) = A[i] + A[i+1] + … + A[j].

1
2
3
4
public int sum(int i, int j)
{
    return i > 1 ? sum(j) - sum(i-1) : sum(j);
}

Igualmente podríamos estar interesados en el valor actual en la alcancía i, o sea, no en la suma de los valores acumulados desde la alcancía 1 hasta la i-esima, sino solamente el valor en esa alcancía. Esto lo podemos calcular fácilmente como sum(i) – sum(i-1).

Actualizar las cantidades

En este caso queremos agregar una moneda con valor v a la i-esima alcancía. También podemos sacar monedas de la i-esima alcancía.

Para esto, cambiamos el valor en el i-esimo elemento del árbol  y debemos notificar a todos los elementos que son responsables de el que ha ocurrido un cambio en el valor. Por ejemplo, si agregáramos una moneda en la alcancía 2, tendríamos que notificar a la 4 y a la 8 de este cambio  ya que ambas son responsables por la 2. Esto mantiene el árbol sincronizado. La forma de hacerlo es actualizar el valor en la posición i, y moverse hacia adelante en el árbol a todos los responsables haciéndoles saber que el elemento fue actualizado.

1
2
3
4
public void update(int i, int value)
{
    for(; i < T.length; i+= lowbit(i)) T[i] += value;
}

En caso de que estemos agregando una moneda con valor v, el valor de value sera positivo. Si estamos sacando una cantidad v, el valor sera negativo.

Construir el árbol

Ya hemos visto como hacer las operaciones fundamentales con el árbol de Fenwick, pero no hemos visto como construirlo! Precisamente el árbol se construye a partir de la operación update.

1
2
3
4
5
public void build(int[] A)
{
    int[] T = new int[A.length + 1];
    for(int i=0; i < A.length; i++) update(i+1, A[i]);
}

Y esto es todo, amigos. El árbol de Fenwick es una estructura muy eficiente, sin embargo sencilla. El concepto no es difícil de entender, y aun sin comprenderlo totalmente, con solo saber como utilizarla, podemos resolver muchísimos problemas. Ademas, se puede extender con facilidad a problemas de varias dimensiones, pero vamos a dedicar otro post completamente a ese tema.

Felices códigos!

Referencias

es.wikipedia.org/wiki/%C3%81rbol_binario_indexado

olds.blogcn.com/wp-content/uploads/67/6754/2009/01/bit.pdf

community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

comeoncodeon.wordpress.com/2009/09/17/binary-indexed-tree-bit/

www.algorithmist.com/index.php/Fenwick_tree

www.swageroo.com/wordpress/little-known-awesome-algorithms-fenwick-range-trees-rapidly-find-cumulative-frequency-sums/

gborah.wordpress.com/2011/09/24/bit-indexed-tree-fenwick-tree/

Problemas

spoj.pl/problems/INVCNT/

www.spoj.com/problems/YODANESS/

uva.onlinejudge.org/external/119/11926.pdf

uva.onlinejudge.org/external/115/11525.pdf

coj.uci.cu/24h/problem.xhtml?abb=1850

coj.uci.cu/24h/problem.xhtml?abb=2125

Visto en http://prodeportiva.wordpress.com

Post to Twitter

This entry was posted in Concursos de Programación, Estructuras de datos, Programacion, Técnicas de programación and tagged , , , , , . Bookmark the permalink.

One Response to Árbol de Fenwick

  1. Miguel says:

    Me lio un poco con la imagen, cuando pones A(i) ¿no sería en realidad A(i-1)?, ya que la primera posición del vector A es la cero, aunque en el vector del árbol T sería la 1.

Deja un comentario

Tu dirección de correo electrónico no será publicada.

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>