Tenemos un arreglo de $N \leq 10^5$ enteros. Nos llegan $Q \leq 10^5$ eventos, que pueden ser de dos tipos: Tipo 1. (Actualización) Nos dan un valor $v$ y una posición $i$ y nos piden cambiar el valor de la posición $i$ del arreglo por el nuevo valor $v$. Tipo 2. (Query de rango) Nos dan dos posiciones $a$ y $b$ y nos preguntan el menor valor del arreglo entre las posiciones $a$ y $b$. * En estos problemas conviene que el rango sea incluyendo a $a$ pero no a $b$, esto nos va a ahorrar muchos $+1$ y $-1$ molestos. Es decir, que el rango sea $[a, b)$. Si el problema no me da rango de este tipo, lo más cómodo es transformarlo a un rango de este tipo apenas los leemos de la entrada así no nos preocupamos más por este detalle.

Por ejemplo, el arreglo inicial puede ser: $[1, 2, 3, 4, 7]$ Nos llega un evento de actualización que actualiza la posición $3$ (recordar que las posiciones las numeramos desde $0$) al valor $-1$. El arreglo queda: $[1, 2, 3, -1, 7]$ 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 $2$ que es el mínimo en el rango que contiene los valores $[2, 3]$. 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.

La idea es poder resolver ambos tipos de queries en $O(log N)$, para eso usaremos una estructura de datos a la que denominamos segment tree.

El segment tree es escencialmente un árbol binario completo. Un árbol binario completo es un árbol con un nodo raiz y donde cada nodo tiene $2$ hijos o es una hoja. El nivel de un nodo es la distancia a la raiz, estando la raiz en el nivel 0, sus hijos en el nivel 1, los hijos de los nodos de nivel 1 en el nivel 2 y así sucesivamente. Y las hojas están todas en el mismo nivel. En este árbol, cada hoja representa una posición del arreglo del problema, de manera que si dibujamos el árbol por niveles, las hojas quedan ordenadas como las posiciones del arreglo que representan de izquierda a derecha. Como un árbol binario completo tiene una cantidad de hojas potencia de $2$ pero el arreglo puede ser de cualquier tamaño, conviene extender el arreglo agregando posiciones al final hasta que quede de longitud potencia de $2$. Notar que al hacer esto el tamaño del arreglo a lo sumo se duplica. Esto nos dice que si procesamos un evento en $O(logN')$ con $N'$ el tamaño del arreglo extendido y $N' < 2N$, entonces $O(logN')$ es $O(logN)$. Por lo que basta probar que podremos procesar las queries en tiempo logaritmico en el tamaño dle arreglo extendido.

* En realidad no hace falta que árbol binario sea completo y se podría modelar de manera que no haya que extender el arreglo, pero es más cómodo trabajar con el árbol completo que posee propiedades buenas como que cada nodo no hoja tiene siempre dos hijos.

Cada nodo no hoja tiene ciertas hojas que cuelgan de él. Todas estas hojas representan un rango de posiciones del arreglo de tamaño potencia de $2$. Este tamaño depende del nivel del nodo, duplicandose a medida que subimos un nivel en el árbol. Un nodo no hoja representará el rango de posiciones de las hojas que cuelgan de él.

La idea será guardar en cada nodo del árbol, el resultado de la query de rango para el rango de posiciones que representa el nodo. Si el nodo es una hoja, guardamos el resultado de la query para el rango que contiene la única posición que representa la hoja. Para este problema, en las hojas guardamos los números del arreglo y en los otros nodos guardamos el mínimo de los números de las hojas que cuelgan de él.

Esto es todo en cuanto a la estructura del segment tree. Lo que nos queda ver es como resolvemos los distintos eventos de forma eficiente y cómo esta estructura nos ayuda para hacerlo.