Segment trees

Consulta de rango Y update puntual, ambos O(log n). Niégate al dilema del array de "consulta rápida O update rápido".

Un árbol de agregados por rango

• Raíz = suma de todo el array; hijos = mitades; hojas = elementos
• Consulta [i,j]: nodo completamente dentro → tomas su suma; parcial → se parte; fuera → se salta
• Cualquier rango = O(log n) segmentos canónicos
• Update: arreglas los O(log n) ancestros de un solo camino

Mira cómo se descompone una consulta

Suma de [2:6] = 3 segmentos canónicos (verde), no 5 lecturas de elementos.

Gana en cargas de trabajo mixtas

50/50 consultas/updates: el segment tree es 6× más rápido que el array en crudo, 100× más rápido que las prefix sums.

Cuándo sí (y cuándo no)

• Sí: datos mutables + consultas de rango (suma/mínimo/máximo/gcd), lazy propagation para updates de rango
• No, datos estáticos: prefix sums (consulta O(1))
• No, solo sumas de prefijo: Fenwick tree (el siguiente — más ligero)

Para llevar

Gana por no tener ninguna operación lenta. Haz benchmark de la carga de trabajo, no de una sola operación. Sigue: el Fenwick tree — el especialista flaco en sumas.