En el manual anterior vimos cómo hacer calcular actualizaciones de un sólo valor en un árbol de segmentos en $\mathcal{O}(\log n)$. Aquí veremos una técnica, denominada lazy propagation, que permite hacer actualizaciones en intervalos en $\mathcal{O}(\log n)$ por actualización.

El árbol de segmentos, como otras estructuras de datos arborescentes, puede implementarse definiendo una clase “Nodo” donde se guarde la información de cada nodo y punteros a sus hijos, pero existe una forma de implementarlo más sencilla. La idea importante es la siguiente: la información se guarda en un array y cada nodo tiene una posición correspondiente donde está guardada su información.

El Árbol de Segmentos / Segment Tree es una estructura de datos que sirve para gestionar de forma eficiente consultas de información y actualizaciones sobre intervalos de un array. Un ejemplo es el problema de Range Minimum Query, es decir, consultar el mínimo valor del array en un intervalo.