Herramientas de usuario
algoritmos-oia:estructuras:segment-tree
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:estructuras:segment-tree [2020/05/25 23:17] ariel [Query de rango (implementación)] |
algoritmos-oia:estructuras:segment-tree [2020/06/03 23:27] (actual) ariel [Caso General] |
||
|---|---|---|---|
| Línea 152: | Línea 152: | ||
| </code> | </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. | ||
algoritmos-oia/estructuras/segment-tree.1590448643.txt.gz · Última modificación: 2020/05/25 23:17 por ariel
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
