Un árbol de segmentos guarda un resumen de cada bloque de posiciones: las hojas tienen valores sueltos y cada padre combina a sus dos hijos. Sirve cualquier operación asociativa con elemento neutro, como la suma con 0, el mínimo con infinito, el máximo o el mcd con 0. Una pregunta de rango combina entonces O(log n) bloques, y una actualización puntual recalcula un solo camino desde una hoja hasta la raíz.
La versión de abajo arriba cabe en pocas líneas: hojas de n a 2n - 1 y el padre i = combinar(2i, 2i + 1). Úsala cuando un árbol de Fenwick no basta, porque la operación no se puede deshacer restando (mínimo, máximo, mcd) o porque necesitas buscar dentro del árbol, por ejemplo la primera posición cuyo valor es al menos x.
Cuando las actualizaciones cubren rangos enteros, añade propagación diferida: un nodo cubierto por una actualización anota el cambio y solo se lo pasa a sus hijos cuando alguien los necesita. En una entrevista, di primero la función de combinación y su elemento neutro, y después el coste de actualizar y de consultar.
Una actualización puntual recalcula un camino desde la hoja hasta la raíz.