Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:estructuras:segment-tree [2020/05/21 00:04]
ariel [Esctructura]
+++ algoritmos-oia:estructuras:segment-tree [2020/06/03 23:27] (actual)
ariel [Caso General]
@@ Línea 11: / Línea 11: @@
 $[1, 5, 3, -1, 2, -3]$
 En este caso no debemos devolver nada, solo desde ahora tener en cuenta que el valor de la posición cambió para los futuros eventos.
-Ahora nos llega un evento de query de rango para el rango $[1, 3)$, debemos devolver el valor $3$ que es el mínimo en el rango que contiene los valores $[5, 3]$.
+Ahora nos llega un evento de query de rango para el rango $[1, 5)$, debemos devolver el valor $-1$ que es el mínimo en el rango que contiene los valores $[5, 3, -1, 2]$.
 Y así, nos prodrían ir llegando más eventos que cambian valores y preguntan por rangos. No hay ninguna restricción en las cantidades de eventos de cada tipo ni el orden en el que llegan.
@@ Línea 43: / Línea 43: @@
 ===== Query de actualización =====
 Cuando llega un evento de actualización que nos pide asignar el valor $v$ a la posición $p$ del arreglo, no nos alcanza con sólo actualizar el arreglo. Tambien queremos que nuestra estructura de segment tree mantenga la propiedad de que cada nodo guarda el valor del mínimo de las hojas que cuelgan de él. Los únicos nodos que pueden llegar a cambiar son los nodos que representan al mínimo de un rango que contiene la posición $p$, es decir, los nodos de los que cuelga la hoja de la posición $p$. Notamos que estos nodos son los nodos del camino de la hoja de la posición $p$ a la raiz. Luego, sólo tenemos que actualizar el valor de estos. Al igual que al inicializar el árbol, podemos hacerlo de abajo hacia arriba facilmente. A la hoja de la posición $p$ le guardamos el nuevo valor $v$ y a medida que subimos por el camino, guardamos en cada nodo el mínimo de sus dos hijos. De esta manera, reestablecemos el invariante del segment tree de que cada nodo contiene el mínimo de su rango correspondiente.
+{{ algoritmos-oia:estructuras:segment-tree-update-1.png?nolink&600 |}}
+Si aplicamos la actualización del ejemplo, que cambia la posición $3$ con el valor $-1$, el árbol queda así. Vemos en azul los nodos con un intervalo que contiene la posición $3$ en los que tuvimos que revisar si hacia falta actualizar su valor.
 En total tuvimos que actualizar un nodo por nivel, pero un árbol binario completo de $N$ nodos tiene $log(N)+1$ niveles. Por lo que la complejidad de actualizar todo el camino es $O(log N)$ y procesamos el evento en el tiempo que queríamos.
@@ Línea 54: / Línea 57: @@
   - Algunos nodos que cuelgan del nodo están en $[a, b)$ y otros no. En este caso, no podemos elegir este nodo pero vamos a tener que elegir algunos de sus hijos para cubrir los nodos de $[a, b)$ que sí cuelgan de este nodo. Lo que hacemos en este caso es agregar a sus dos hijos a la lista de nodos a revisar.
-Realizamos este procedimiento hasta que no queden nodos en la lista por revisar y habremos obtenido una lista de nodos que cubren todo el rango $[a, b)$. Si en total revisamos $O(logN)$ nodo, logramos lo que queríamos, ya que la lista de nodos elegidos son algunos de los que revisamos, por lo que tambien son $O(logN)$. La clave para ver que revisamos pocos nodos es ver que por nivel revisamos a lo sumo 4 nodos. Notemos que por cada 2 nodos que revisamos en un nivel, provienen de una nodo del nivel de arriba que cayó en el último caso. Pero si un nodo cae en último caso, es porque le cuelgan algunos nodos del rango y otros no. Pero esto sólo puede pasar si le cuelga alguno de los bordes del rango $[a, b)$. Es decir, le cuelga el nodo $a$ o el nodo $b$. Pero por nivel hay un solo nodo del que cuelga el nodo $a$ y uno sólo del que cuelga el nodo $b$ (podrían ser el mismo). Por lo que hay como mucho dos nodos que caen en el tercer caso por nivel y por lo tanto revisamos a lo sumo 4 nodos por nivel. Luego, en total revisamos a los sumo $4 logN$ nodos que es $O(logN)$ y luego respondemos la query en $O(logN)$.
+Realizamos este procedimiento hasta que no queden nodos en la lista por revisar y habremos obtenido una lista de nodos que cubren todo el rango $[a, b)$.
+{{ algoritmos-oia:estructuras:segment-tree-query-1.png?nolink&600 |}}
+Acá tenemos como queda el algoritmo para la query del ejemplo, donde preguntamos por el rango $[1, 5)$. Los nodos rojos son los que cayeron en el primer caso y fueron descartados. Los nodos verdes son los que cayeron en el segundo caso y fueron los elegidos para cubrir el rango. Los nodos azules son los que cayeron en el tercer caso y revisamos a sus dos hijos. Por último, los nodos blancos son los que no hizo falta revisar.
+Queda ver que el algoritmo es lo suficientemente rápido.
+Si en total revisamos $O(logN)$ nodo, logramos lo que queríamos, ya que la lista de nodos elegidos son algunos de los que revisamos, por lo que tambien son $O(logN)$. La clave para ver que revisamos pocos nodos es ver que por nivel revisamos a lo sumo 4 nodos. Notemos que por cada 2 nodos que revisamos en un nivel, provienen de una nodo del nivel de arriba que cayó en el último caso. Es decir se pueden emparejar de modo que cada par tnega el mismo padre azul. Pero si un nodo cae en último caso (es azul), es porque le cuelgan algunos nodos del rango y otros no. Pero esto sólo puede pasar si le cuelga alguno de los bordes del rango $[a, b)$. Es decir, le cuelga el nodo $a$ o el nodo $b$. Pero por nivel hay un solo nodo del que cuelga el nodo $a$ y uno sólo del que cuelga el nodo $b$ (podrían ser el mismo). Por lo que hay como mucho dos nodos azules por nivel y por lo tanto revisamos a lo sumo 4 nodos por nivel. Luego, en total revisamos a los sumo $4 logN$ nodos que es $O(logN)$ y luego respondemos la query en $O(logN)$.
+===== Implementación sobre arreglo =====
+Si bien es posible implementar el segment tree sobre alguna estructura de grafos o árboles usual, suele ser más cómodo y fácil de implementar directamente guardando los nodos sobre un arreglo. La idea será crear un arreglo $A$ de tamaño $2N$ con $N$ el tamaño del arreglo original ya extendido. Numeramos los nodos del arbol de arriba hacia abajo y de izquierda a derecha, de modo que la raiz es el nodo $1$ y las hojas van del nodo $N$ al $2N-1$. El número de un nodo, representa la posición del arreglo $A$ en donde guardamos el valor del nodo.
+* Notar que la posición $0$ del arreglo queda sin usar. Hacemos esto para que las cuentas queden más simples más adelante.
+Se ve que los hijos de un nodo $i$ son el $2i$ y el $2i+1$ y el padre de el nodo $j$ es el nodo $\lfloor j/2 \rfloor$, es decir la parte entera de $j/2$. Con esta información, ya podemos recorrer el árbol como queramos sin necesidad de guardar las aristas explicitamente.
+===== Inicializar el Segment Tree (implementación) =====
+Lo primero que hacemos es buscar la menor potencia de $2$ mayor a $N$ para saber cuanto extender el arreglo original. Luego guardamos los valores del arreglo original en las posiciones de $N$ a $2N-1$. Por último recorremos de atras para adelante las posiciones de la $1$ a la $N-1$ guardamos el mínimo de los dos hijos como explicamos antes.
+<code cpp>
+vector<int> initSegmentTree(vector<int> arregloInicial) {
+    int n = 1;
+    while(n < (int) arregloInicial.size()) {
+        n *= 2;
+    }
+    // Calculamos el tamaño del arreglo extendido
+    vector<int> segmentTree(2*n, INF);
+    for(int i = 0; i < (int) arregloInicial.size(); i++) {
+        segmentTree[i+n] = arregloInicial[i];
+    }
+    // Llenamos las hojas con los valores del arreglo inicial, las hojas restantes quedan con valor INF
+    for(int i = n-1; i > 0; i--) {
+        segmentTree[i] = min(segmentTree[2*i], segmentTree[2*i+1]);
+    }
+    // Calculamos los valores de los nodos intermedios
+    return segmentTree;
+}
+</code>
+===== Evento de actualización (implementación) =====
+Como vimos, para actualizar el árbol despues de cambiar el valor de una posición $p$, debemos actualizar los nodos del camino hacia la raiz de abajo hacia arriba. Esto se puede hacer empezando por el nodo que representa la posición $p$ que es el $p+n$ y recorriendo sus padres hasta llegar a la raiz (nodo $1$).
+<code cpp>
+void updateSegmentTree(vector<int>& segmentTree, int posicion, int valor) {
+    int n = segmentTree.size()/2;
+    int nodoActual = posicion+n;
+    segmentTree[nodoActual] = valor;
+    while(nodoActual > 1) {
+        nodoActual /= 2; // Voy al padre
+        segmentTree[nodoActual] = min(2*nodoActual, 2*nodoActual+1); // Actualizo
+    }
+}
+</code>
+===== Query de rango (implementación) =====
+Para implementar la query de rango que pregunta por el mínimo en un rango $[a, b)$, vamos a hacer algo similar a lo que explicamos antes, pero implementado de forma recursiva. La idea será que cada nodo devuelva el mínimo de los nodos verdes que cuelgan de él. Esto es equivalente al mínimo entre la intersección entre el rango $[a, b)$ y el rango que representa el nodo. Como del nodo raiz cuelgan todos los nodos verdes (o el rango que representa la raiz es todo el arreglo y la intersección con $[a, b)$ es todo $[a, b)$) la respuesta de la query será el resultado que devuelva el nodo raiz. La recursión hará lo siguiente segun el color del nodo:
+  - Para un nodo verde, el resultado es el valor del nodo, ya que todos los hijos de un nodo verde son blancos.
+  - Para un nodo rojo, los hijos son todos blancos, por lo que no hay ningun nodo verde que cuelgue de él y el mínimo queda indefinido. Podemos devolver un valor como $\infty$ que no moleste con el mínimo.
+  - Para un nodo azul, llamamos recursivamente a sus dos hijos y devolvemos el mínimo de la respuesta de ambos hijos.
+Lo que queda es ver eficientemente de qué color es un nodo, para eso debemos saber cual es el rango que representa. Lo más fácil para esto es agregar dos parámetros a la recursión que guarden los extremos que representen al nodo. Cuando llamamos recursivamente a los hijos, los llamamos con la mitad izquierda y la mitad derecha del intervalo segun si llamamos la recursión sobre el hijo izquierdo o el hijo derecho.
+Una vez que tenemos que el nodo representa un intervalo $[c, d)$,
+  * Es un nodo verde si $[a, b)$ está todo adentro de $[c, d)$ que pasa si $a \geq c$ y $b \leq d$
+  * Es un nodo rojo si $[a, b)$ y $[c, d)$ no tienen elementos en común. Esto pasa si $[a, b)$ está todo a la izquierda de $[c, d)$ o $[a, b)$ está todo a la derecha de $[c, d)$. El primer caso ocurre si $b \leq c$ y el segundo si $d \leq a$.
+  * Es azul si no es ni rojo ni verde.
+Con esto ya podemos implementar la query:
+<code cpp>
+int querySegmentTree(vector<int>& segmentTree, int a, int b) {
+    int n = segmentTree.size()/2;
+    return querySegmentTreeEnNodo(segmentTree, 1, 0, n, a, b);
+    // inicio la recursión sobre la raiz (nodo 1) que representa el rango [0, N)
+}
+int querySegmentTreeEnNodo(vector<int>& segmentTree, int nodoActual, int extremoIzq, int extremoDer, int a, int b) {
+    if(a >= extremoIzq && b <= extremoDer) {
+        // Si estoy en un nodo verde
+        return segmentTree[nodoActual];
+    }
+    if(b <= extremoIzq || extremoDer <= a) {
+        // Si estoy en un nodo rojo
+        return INF;
+    }
+    // Si estoy en un nodo azul
+    int puntoMedio = (extremoIzq + extremoDer) / 2;
+    return min(querySegmentTreeEnNodo(segmentTree, 2*nodoActual, extremoIzq, puntoMedio, a, b), querySegmentTreeEnNodo(segmentTree, 2*nodoActual+1, puntoMedio, extremoDer, a, b));
+}
+</code>
+===== Caso General =====
+Hasta ahora siempre abordamos el problema que tiene como query de rango hallar el mínimo para ese rango. Sin embargo, esta estructura no sólo funciona para el mínimo sino para muchos casos más de queries de rango. Si el problema se basa sobre un arreglo al que se le aplican eventos de actualización y queries de rango, ésta estructura suele ser útil. Lo único que necesitamos es que para la query de rango, se pueda calcular facilmente la respuesta para un rango dada la respuesta para dos subrangos que lo forman. Más formalmente, debemos poder dar la respuesta para el rango $[a, c)$ dadas las respuestas para el rango $[a, b)$ y $[b, c)$.
+Algunos ejemplos de queries de rango que cumplen esta propiedad son: mínimo valor, máximo valor, suma, cualquier operación de bits (AND, OR, XOR).
+¿Qué debemos cambiar de la implementación para una operación de rango cualquiera?
+Como dijimos antes, tenemos que tener una operación que nos permita combinar el resultado de dos rangos que se tocan para obtener el resultado del rango de los dos combinados, a esta operación la podemos llamar el //merge// de dos intervalos. Luego, basta reemplazar en el código, los lugares que dice "min" por la operación de merge.
+Algo que tambien tenemos que cambiar es el valor "default" que le dimos al resultado de los nodos rojos. Necesitamos algo que sea un neutro para el merge, es decir, un valor tal que si lo mergeamos con otro valor siempre el resultado es el otro valor. Para el máximo podría ser $-\infty$ y para la suma $0$. Sin embargo, peude pasar que no exista este neutro. En este caso podemos devolver un valor especial "indefinido" para los nodos rojos y tener cuidado para que cuando uno de los hijos de un nodo azul es rojo, devolver siempre el valor del otro hijo.

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página