Diferencias

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

--- algoritmos-oia:estructuras:segment-tree [2020/06/03 23:22]
ariel
+++ algoritmos-oia:estructuras:segment-tree [2020/06/03 23:27] (actual)
ariel [Caso General]
@@ Línea 159: / Línea 159: @@
 ¿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