Diferencias

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

--- algoritmos-oia:estructuras:segment-tree [2020/05/24 15:24]
ariel [Inicializar el Segment Tree (implementación)]
+++ algoritmos-oia:estructuras:segment-tree [2020/06/03 23:27] (actual)
ariel [Caso General]
@@ Línea 94: / Línea 94: @@
     }
     // 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