Árbol de Fenwick 2D

El Árbol de Fenwick (conocido también como BIT) es una estructura muy eficiente para calcular sumas en intervalos. En este post vamos a ver como podemos usarlo en un problema de dos dimensiones. El problema es el siguiente:

Supongamos que tenemos un terreno rectangular que representa un sembrado de tamaño n × m. Podemos sembrar plantas en distintos puntos de este terreno, y estamos interesados en saber cuantas plantas hay en una porción dada del terreno.

Para resolver este problema, necesitamos definir 2 operaciones:

  1. Consulta. Esta operación calcula, dada una porción del terreno, cuantas plantas hay dentro de esa porción.
  2. Actualización. Esta operación agrega una o varias plantas en una posición dada del terreno.

Estas son operaciones similares a las del BIT, pero en este caso las vamos a realizar sobre un arreglo bidimensional. Esto lo podemos hacer creando un BIT donde cada elemento del árbol, sera a su vez un BIT convencional.

BIT 2D
BIT 2D

Al crear un BIT 2D, podemos realizar las operaciones que necesitamos para resolver el problema. En este caso, cada elemento del BIT sera responsable por un intervalo de filas en el arreglo bidimensional, y contendrá otro BIT que sera responsable por un intervalo de columnas. Al crear un BIT 2D a partir del arreglo bidimensional, cada elemento (i, j) del arreglo almacenara la suma del rectángulo desde (0, 0) hasta (i, j).

Consultando sumas acumuladas

Con este diseño podemos responder fácilmente la suma acumulada en el rectángulo desde (0, 0) hasta (i, j). Similar al BIT convencional, vamos a recorrer los nodos responsables de las filas, y de cada nodo vamos a recorrer los responsables en el BIT que este contiene. Suponiendo que la información sea almacenada en el arreglo bidimensional T[i, j], la operación de consulta quedaría así:

public int sum(int i, int j)
{
    int result = 0;
    for(int r = i; r > 0; r-= lowbit(r))
        for(int c = j; c > 0; c-= lowbit(c))
            result+= T[r][c];
    return result;
}

Esta operación es O(log n × log m), ya que recorremos los responsables en las filas, y para cada uno de ellos, los responsables en el BIT interno. Si queremos consultar la suma en un rectángulo dentro dentro del arreglo, tenemos que realizar otros cálculos.

rectangle2

Si deseamos calcular el valor dentro del rectángulo verde, tendríamos que calcular la suma desde la posicion (0, 0) hasta la esquina inferior derecha de este rectángulo (A)  y restarle los valores acumulados en los rectángulos 1 y 2 (B y C); y sumarle el valor del rectángulo 3, ya que este esta comprendido dentro de 1 y 2 y lo restamos dos veces al quitar los valores de ellos (D).

public int sum(int i, int j, int i2, int j2)
{
    int a = sum(i2, j2) + sum(i-1, j-1);
    int b = sum(i2, j-1) + sum(i-1, j2);
    return a-b;
}

Cambiar los valores

Para esta operación  tenemos que cambiar el valor en la posición que queremos, y luego recorrer todos los nodos responsables de la fila en que se encuentra la posición, y en cada BIT contenido en la fila, actualizar los valores en los elementos responsables.

public void update(int i, int j, int v)
{
    for(int r = i; r < n; r += lowbit(r))
        for(int c = j; c < m; c += lowbit(c))
            T[i][j] += v;
}

Esta operacion es O(log n × log m) y su analisis es similar a la operacion de consulta.

Con estas operaciones podemos resolver el problema planteado. De manera similar podemos extender el BIT a mas dimensiones, y asi resolver problemas mas complejos.

Felices codigos!

Referencias

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

Problemas

http://coj.uci.cu/24h/problem.xhtml?abb=1904

http://www.spoj.com/problems/MATSUM/

Anuncios

2 comentarios en “Árbol de Fenwick 2D

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s