Segment Tree es una estructura de datos para range queries y range updates sobre un array. Usa divide and conquer: divide el array en segmentos, almacena información agregada en cada nodo, y combina resultados en O(log n).

Es la herramienta estándar para problemas como “suma en rango”, “mínimo en rango”, o “contar elementos distintos en rango”.

Estructura

Un segment tree es un árbol binario donde:

• Cada nodo representa un segmento [L, R] del array.
• La hoja i almacena arr[i].
• El nodo interno almacena la combinación de sus hijos (suma, mínimo, máximo, gcd, etc.).

Build

build(node, L, R):

• Si L == R: hoja = arr[L].
• Si no: mid = (L+R)//2, build(left, L, mid), build(right, mid+1, R), luego tree[node] = combine(tree[left], tree[right]).

Complejidad: O(n) porque hay ~2n nodos.

Range Query

query(node, L, R, ql, qr):

• Si [L,R] completamente dentro de [ql,qr]: retorna tree[node].
• Si no intersecta: retorna identity element.
• Si se superpone: recursiona en hijos y combina.

Complejidad: O(log n) porque visita a lo sumo 4 log n nodos.

Range Update con Lazy Propagation

Para actualizar un rango [ql,qr] con valor val:

• Lazy node: almacena el update pendiente para el segmento completo.
• Push: cuando un nodo con lazy se visita, propaga el update a sus hijos.
• Apply: actualiza el nodo actual según la operación.

Complejidad: O(log n) con lazy propagation.

Ejemplo

Array: [1, 3, 5, 7, 9, 11], query suma en rango [1, 4] (índices 1-based: 3+5+7+9 = 24).

Segment tree combina nodos que cubren exactamente el rango.

Comparación

Aplicaciones

• Range queries — suma, mínimo, máximo, gcd en rango
• Range updates — suma en rango, asignación en rango
• K-th order statistics — con merge sort tree
• Distinct elements in range — con persistente segment tree
• Enseñanza — introduce divide and conquer y lazy propagation

Trayectoria de Práctica

1. Implementa segment tree para range sum; traza query [1,4].
2. Añade range update con lazy propagation.
3. Extiende a range minimum query.
4. Investiga iterative segment tree (array-based, no recursivo).
5. Investiga fenwick tree: ¿cuándo es más simple y suficiente?