Diferencias

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

--- 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:22]
ariel
@@ Línea 152: / Línea 152: @@
 </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.

OIA-Wiki