La solución para este problema es incluir los números mas grandes en el arreglo en las posiciones donde sean mas consultados, para que contribuyan la mayor cantidad al resultado total. Para esto hay que calcular cuales son las posiciones que mas aparecen en las consultas. Esto se puede lograr usando un BIT e introducir cada intervalo de consulta como update(l, 1) y update(r+1, -1). Luego podemos consultar en el BIT dada una posición i, cuantos intervalos contienen esa posición Ordenamos las posiciones descendentemente por la cantidad de intervalos que la contienen, y los números del arreglo en orden descendiente. Finalmente, cada numero en el arreglo original contribuye a la suma con n×T[i], donde T[i] es el valor de la cantidad de intervalos que contienen la posición i.
Existe otra forma de calcular la cantidad de intervalos que contienen una posición dada, que no requiere de ninguna estructura especial. Esto lo podemos calcular con un arreglo A[i]. Dado un intervalo [l, r], incrementamos A[l] y decrementamos A[r+1].
Después de procesar todos los intervalos, calculamos A[i] = A[1] + A[2] + … + A[i]. Dada una posición i, hay 3 casos:
[l, r] termina antes que i. En este caso, se cancela el incremento en l con el decremento en r, y no se afecta el valor de A[i].
[l, r] comienza después de i. En este caso, el incremento es después de la posición i, por tanto no se afecta su valor.
[l, r] contiene a la posición i. En este caso, solo contamos el valor del incremento en l, ya que r esta después de i.
Esta técnica es mas sencilla y puede ser usada para muchos otros tipos de problemas en los que se requiera tratar con intervalos.
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:
Consulta. Esta operación calcula, dada una porción del terreno, cuantas plantas hay dentro de esa porción.
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
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.
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.
Este problema puede ser resuelto con un árbol de Fenwick. Nos dan el arreglo A como entrada. A partir de este arreglo, podemos crear un BIT de tamaño 10^7. Para cada elemento en A, vamos a insertar 1 en la posición correspondiente en el BIT.
Por ejemplo, en el primer caso, los elementos son [3, 1, 2]. Insertamos 1 en la posición 3, 1 en la 1 y 1 en la 2.
Para responder cuantas inversiones se forman, podemos consultar cada vez que insertemos un numero, cuantos mayores que el se han insertado, esto es, consultar el intervalo [n+1, 10^7] en el BIT. En el ejemplo, después de insertar 1 en 3, tenemos 0 mayores que el, ya que no se ha insertado ninguno después de 3. Al insertar 1 en 1, tenemos 1 mayor que 1, ya que el 3 fue insertado antes. Y al insertar el 2, también tenemos 1 mayor que 2. Para dar la respuesta, sumamos la cantidad de inversiones para cada numero.
Este problema puede ser resuelto usando un árbol de Fenwick, pero en una forma no convencional. Crearemos el árbol del tamaño de la máxima duración de una tarea (10^6), y lo vamos a utilizar para contar cuantas tareas se están ejecutando en un momento dado.
Cada tarea esta representada por el inicio (s) y el final (e). Supongamos que en la posición s del BIT insertamos 1. De esta manera, cuando consultemos cuantas tareas se están ejecutando en el momento s, tendremos 1. Pero dada la estructura de responsabilidades del BIT, si consultamos en cualquier momento mayor que s, también tendremos que hay 1 tarea activa, porque se acumula a lo largo del árbol. La forma de contrarrestar esto, es insertar -1 en la posición e, para que no se propague el valor de la posición e en adelante. De esta manera, cuando consultemos el intervalo [s, e] tendremos 1 tarea activa, y si consultamos fuera del intervalo, tendremos 0.
Con esta idea, cada vez que tengamos una tarea, consultamos su inicio y su final en el BIT para saber si hay alguna ejecutándose en estos momentos, y si es así, tenemos un conflicto. De lo contrario, la insertamos en el árbol haciendo update(s, 1) y update(e, -1). Hay que tener cuidado especial con los puntos de inicio y final, ya que dos tareas si pueden «tocarse», pero no pueden solaparse.
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.
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:
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.
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:
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.
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.
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.
Programacion Deportiva 