Fenwick Trees (Arboles Binarios 2)

Fecha: September 6th, 2009 | Categoría: Informatica | No Comments »

La Heap es una estructura de datos indispensable para todo programador/algoritmista que pretenda competir en lugares como Topcoder, ACM-ICPC, Google Code Jam, IOI, etc. Fué revisada en el post anterior (heaps, arboles binarios 1)

Hay una estructura de datos que ha ganado popularidad últimamente, como otros árboles binarios, y ésta es el Árbol de Fenwick.

El Árbol de Fenwick (fentree de ahora en adelante) nos es útil cuando necesitamos mantener la suma de números en un arreglo, entre dos posiciones, con actualizaciones en los números. La solución trivial, mantener la suma desde el principio hasta cada nodo, es muy rápida para las consultas (O(1)) pero muy lenta para las actualizaciones (O(N)).

El fentree lo que hace es responder a estas dos operaciones en O(\log N), construyendo encima de nuestro array la siguiente estructura:

  • Arriba que el array, vamos a guardar N/2 elementos, un elemento por cada dos de nuestro array original, conteniendo la suma de los dos "hijos" (acá se vé un vistazo de a donde quiero llegar). Lo podemos almacenar en un nuevo array.
  • Construímos la misma cosa para nuestros nuevos arrays hasta que nos quede de un solo elemento.

construye1Luego:

construye2Y por último:

construye3

¿Cuál es la magia de esto? Si queremos saber la suma desde el principio hasta cierto numero, nos vamos a fijar en elementos de distintas "alturas". Cada uno de estos elementos nuevos en distintas alturas (ejercicio: demostrar que hay ceiling(\log N) alturas) corresponden a la suma de valores de 2^h elementos. Entonces, buscamos la primer potencia de 2 que no sea mayor al número hasta el que queremos llegar y vamos guardando ese valor. De los elementos que no son hijos (ni descendientes) de este elemento que agarramos, vamos a agarrar el de mayor altura que no tome elementos más a la izquierda de nuestro target. Así, hasta que lleguemos hasta nuestro elemento.

Veamos dos ejemplos:

Para obtener la suma de todos los valores pintados de rojo, tenemos guardada la información en los cuadraditos pintados también de rojo:

forma

Otro ejemplo:

forma1

La operación de alterar un valor necesita alterar un elemento adicional por cada "nivel" (demostrar que en un nivel, sólo un elemento tiene adentro sumada el valor de un elemento inferior).

OBSERVACIÓN!

Estamos guardando información de más. Vamos a eliminar algunos nodos aprovechandonós de esta propiedad:

observa1

Y nuestro árbol va a cambiar de forma (al ejemplo anterior, del árbol grande, lo completé hasta la siguiente potencia de 2):

elimina1 => elimina2

Y después, recursivamente para los niveles superiores:

elimina3Hasta que nos queda esto:

elimina4

Vamos a ponerle números a la cosa para clarificar:

binarios

Querys en python:

Para la query, usamos el truco de "eliminar el último bit". Si a una variable "a" le queremos sacar el último bit, negamos todo "a" (los 1 se vuelven ceros y viceversa) y sumamos 1; luego hacemos un "and" binario con la variable original este valor obtenido. Cuando sumamos uno a la negación, vamos a estar acarreando en la suma un 1 hasta que haya un cero en la negación (el primer 1 del número original). Aprovechandonos del sistema representacional de los números en la mayoría de las arquitecturas como el complemento a cero, podemos hacer esta operacion a-=((~a)+1)&a) como a&=-a

  1. def query(n):
  2.     respuesta = 0
  3.     while n != 0:
  4.         respuesta += fentree[n]
  5.         n &= -n
  6.     return respuesta

Modificaciones

Notamos que cuando alteramos un valor, tenemos que ir "subiendo" hacia la derecha hasta el próximo valor mayor de distancia en bits 1.

  1. def add(pos, value):
  2.     while pos != maximo:
  3.         fentree[pos] += value
  4.         pos += pos&(-pos)

En el próximo post, Range Minimum Queries y (tal vez) Wavelet Trees.