🧱 Segment tree

Estructura de datos · Se implementa a mano · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras

📍 Dónde se aprende: módulo 20 de la Ruta de Aprendizaje.

El problema: consultar un arreglo que cambia

Un segment tree, o árbol de segmentos, permite consultar intervalos de un arreglo y cambiar sus elementos sin recorrer todo el arreglo en cada operación. Aquí lo construiremos desde cero para responder sumas. Al final veremos cómo adaptar la misma idea a mínimos.

Para seguir la explicación necesitas conocer arreglos, funciones y recursión: una función que se llama a sí misma sobre un problema más pequeño. Puedes repasar esa última idea en 09 - Recursión.

Considera este arreglo de ocho valores:

Índice01234567
Valor31425021

Queremos intercalar dos operaciones:

  • Consultar [l,r]: sumar los elementos desde la posición l hasta la r, incluyendo ambos extremos. Por ejemplo, [2,6] suma 4 + 2 + 5 + 0 + 2 = 13.
  • Asignar en una posición: reemplazar su valor. Si hacemos a[4] = 8, la misma consulta [2,6] debe devolver 16.

La solución directa actualiza una casilla en O(1), pero una consulta puede recorrer n elementos. Con q consultas grandes, eso llega a O(nq). Queremos guardar resultados parciales que aceleren las consultas y sean baratos de reparar después de una modificación.

La idea: guardar sumas de mitades

Guardar solo la suma del arreglo completo permite responder [0,7], pero no [2,6]. Guardemos también las sumas de las dos mitades, [0,3] y [4,7]. Dividimos cada mitad de nuevo, hasta llegar a segmentos de un solo elemento.

Esta organización forma un árbol: cada casilla del árbol es un nodo que representa un intervalo. El nodo del arreglo completo se llama raíz. Sus dos hijos representan sus dos mitades. Los nodos de un solo elemento, que ya no se dividen, son las hojas.

Para dividir [l,r], calculamos m = (l + r) / 2, redondeando hacia abajo. Los hijos cubren [l,m] y [m+1,r]. No hay huecos ni elementos repetidos. Esto también funciona si n no es una potencia de dos: por ejemplo, [0,4] se divide en [0,2] y [3,4].

Un árbol de intervalos

Cada nodo guarda la suma de su intervalo. En una hoja copiamos el valor original; en los demás nodos sumamos los resultados de los dos hijos. Para construir el árbol calculamos primero las hojas y combinamos hacia arriba: [0,1] guarda 3 + 1 = 4, [2,3] guarda 4 + 2 = 6, y [0,3] guarda 4 + 6 = 10. La otra mitad, [4,7], suma 8, así que la raíz [0,7] guarda 10 + 8 = 18.

El borde grueso señala los segmentos completos que elegimos para consultar [2,6]. Todos los intervalos del dibujo son cerrados.

[0,0]3[1,1]1[0,1]4[2,2]4[3,3]2[2,3]6[0,3]10[4,4]5[5,5]0[4,5]5[6,6]2[7,7]1[6,7]3[4,7]8[0,7]18Borde grueso: segmentos que aportan 6 + 5 + 2 = 13

Si el diagrama no cabe, deslízalo horizontalmente.

No necesitamos leer cinco hojas: tomamos [2,3], [4,5] y [6,6]. Sus sumas son 6 + 5 + 2 = 13. Son partes disjuntas cuya unión es [2,6].

Las tres decisiones de una consulta

Para cada nodo comparamos su segmento [l,r] con el intervalo pedido:

RelaciónEjemplo al consultar [2,6]Acción para suma
No se tocannodo [0,1]devolver 0
El nodo queda completamente dentronodo [2,3]devolver su resumen, 6
Se superponen parcialmentenodo [4,7]consultar sus dos hijos y combinar

Devolver el resumen de un nodo completo evita recorrer sus hojas. Cuando hay superposición parcial, sus hijos separan el segmento sin repetir elementos. Al combinar sus respuestas obtenemos exactamente la parte solicitada.

Sigamos la consulta [2,6] desde la raíz, sin elegir los segmentos de antemano:

  1. [0,7] se superpone parcialmente: consultamos [0,3] y [4,7].
  2. En [0,3], [0,1] queda fuera y devuelve 0; [2,3] queda completamente dentro y devuelve 6. Esta mitad aporta 0 + 6 = 6.
  3. En [4,7], [4,5] queda completamente dentro y devuelve 5. [6,7] se superpone parcialmente, así que bajamos una vez más.
  4. En [6,7], [6,6] devuelve 2 y [7,7] queda fuera y devuelve 0. Esta parte aporta 2; la mitad derecha aporta 5 + 2 = 7.
  5. La raíz combina ambas respuestas: 6 + 7 = 13.

El cero significa «este segmento no aporta elementos a la suma pedida». No significa que los valores guardados en ese segmento sean cero.

Qué se modifica al cambiar un valor

Si asignamos a[4] = 8, solo cambia la hoja [4,4] y sus antecesores:

SegmentoSuma anteriorSuma nueva
[4,4]58
[4,5]58
[4,7]811
[0,7]1821

Para encontrar la hoja, en cada nodo miramos la posición i que queremos cambiar: si i <= m, vamos al hijo izquierdo; en caso contrario, al derecho. Para i = 4, el camino es [0,7] → [4,7] → [4,5] → [4,4]. Reemplazamos el valor en la hoja y, al volver de las llamadas recursivas, sumamos de nuevo los hijos de cada nodo.

Los demás segmentos no incluyen esa posición, así que sus sumas siguen siendo correctas. La consulta [2,6] pasa de 13 a 16. La propiedad que mantenemos después de construir y después de cada cambio es la misma: cada nodo guarda la suma actual de todos los elementos de su intervalo.

Por qué el costo es logarítmico

La altura es O(log n) porque cada división reduce el segmento aproximadamente a la mitad. Una actualización sigue un único camino de esa altura.

Una consulta puede tomar varios caminos, pero en cada nivel solo los segmentos que contienen los dos extremos pueden quedar parcialmente cubiertos. Los demás se descartan o aportan su resumen sin seguir bajando. Por eso el trabajo total también es O(log n), incluso si el intervalo pedido es muy grande.

OperaciónTiempo o espacio
ConstruirO(n): se calcula cada nodo una vez
Asignar en una posiciónO(log n)
Consultar un intervaloO(log n)
MemoriaO(n): este código reserva 4n casillas

Implementación recursiva y uso

Dos clases de índices que no debemos confundir

El arreglo original usa posiciones desde 0. El árbol se guarda en otro arreglo, t, donde la raíz ocupa la casilla 1. Para un nodo situado en la casilla nd, reservamos la casilla 2 × nd para su hijo izquierdo y 2 × nd + 1 para el derecho. La casilla 0 de t no se usa.

Casilla del árbolIntervalo que representa en este ejemploSuma inicial
t[1][0,7]18
t[2][0,3]10
t[3][4,7]8
t[4][0,1]4
t[5][2,3]6

nd identifica dónde guardamos el resumen; l y r indican qué posiciones originales resume. El número de un nodo no es el índice del elemento consultado. Pasamos [l,r] en cada llamada para no tener que guardarlo también en t.

Un árbol con n hojas tiene 2n−1 nodos, pero esta numeración puede dejar huecos cuando las mitades tienen tamaños distintos. Reservar 4n casillas es una cota segura para esta representación: al completar el árbol hasta la siguiente potencia de dos, el número de casillas necesarias sigue siendo menor que 4n.

El código

El bloque define la estructura SegTree. Usa vector y long long; en un programa de competencia puedes colocar antes #include <bits/stdc++.h> y using namespace std;. Las llamadas de uso van dentro de main.

struct SegTree {                          // suma; cambia el operador para mín/máx/gcd
    int n; vector<long long> t;
    SegTree(int n) : n(n), t(4 * n, 0) {}
 
    void build(const vector<long long>& a, int nd, int l, int r) {
        if (l == r) { t[nd] = a[l]; return; }         // hoja: un solo elemento
        int m = (l + r) / 2;
        build(a, 2*nd, l, m);  build(a, 2*nd+1, m+1, r);
        t[nd] = t[2*nd] + t[2*nd+1];                  // el padre resume a sus dos hijos
    }
    void update(int nd, int l, int r, int i, long long v) {   // a[i] = v
        if (l == r) { t[nd] = v; return; }
        int m = (l + r) / 2;
        if (i <= m) update(2*nd, l, m, i, v);
        else        update(2*nd+1, m+1, r, i, v);
        t[nd] = t[2*nd] + t[2*nd+1];
    }
    long long query(int nd, int l, int r, int ql, int qr) {   // suma en [ql, qr]
        if (qr < l || r < ql) return 0;               // fuera del rango: el neutro
        if (ql <= l && r <= qr) return t[nd];         // dentro: ya está resumido
        int m = (l + r) / 2;
        return query(2*nd, l, m, ql, qr) + query(2*nd+1, m+1, r, ql, qr);
    }
    // wrappers: la raíz es el nodo 1 y cubre todo el rango [0, n-1]
    void build(const vector<long long>& a) { build(a, 1, 0, n - 1); }
    void update(int i, long long v) { update(1, 0, n - 1, i, v); }
    long long query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

Cómo usarlo en el ejemplo

Instrucción dentro de main, en este ordenEfecto
vector<long long> a = {3,1,4,2,5,0,2,1};crear los datos originales
SegTree st(a.size());reservar espacio para el árbol
st.build(a);calcular sus sumas iniciales
cout << st.query(2,6) << '\n';imprimir 13
st.update(4,8);asignar 8 a la posición 4 dentro del árbol
cout << st.query(2,6) << '\n';imprimir 16

Los métodos cortos al final son la interfaz que llamas. Completan los parámetros internos iniciando el recorrido en nd = 1, l = 0, r = n−1. Por ejemplo, query(2,6) llama a query(1,0,7,2,6): los primeros tres argumentos describen el nodo actual y los dos últimos, ql y qr, mantienen el intervalo pedido durante todo el recorrido.

update(4,8) reemplaza el valor por 8; no le suma 8. La estructura mantiene su propia información: no modifica el vector a que usaste para construirla. Cambiar a[4] por separado tampoco actualiza el árbol. Después de build, los cambios que quieras reflejar en las consultas deben pasar por update.

Esta implementación requiere n > 0, un arreglo de construcción de tamaño n y posiciones y consultas válidas: 0 <= i < n y 0 <= l <= r < n. Los valores y sus sumas deben caber en long long.

Pasar de sumas a mínimos

La estructura del árbol y las decisiones de recorrido no dependen de la suma. Podemos guardar otro resumen que se pueda obtener combinando los dos hijos. Para mínimos, el nodo [2,3] guardaría min(4,2) = 2; el [4,5], min(5,0) = 0; y el [6,6], 2. Consultar [2,6] combinaría esos mismos segmentos con min(2,0,2) = 0.

La operación que combina resúmenes debe ser asociativa: agrupar las partes de distintas maneras no debe cambiar el resultado. También necesitamos un elemento neutro para los segmentos que no intersectan la consulta: un valor que no altere el resultado al combinarlo. Para suma es 0 porque x + 0 = x; para mínimo es +∞ porque min(x,+∞) = x.

ResumenCombinar dos hijosRespuesta de un segmento ajeno
Sumax + y0
Mínimomin(x,y)+∞
Máximomax(x,y)−∞
MCDgcd(x,y)0

Para mínimos debes cambiar las combinaciones en build, update y query, la respuesta fuera de rango y la inicialización del arreglo auxiliar. Puedes representar +∞ con LLONG_MAX cuando solo lo comparas con min. Cambiar únicamente el + de la construcción no basta.

Cuándo elegirlo y cómo continuar

El segment tree resulta útil cuando se intercalan modificaciones puntuales y consultas de rangos con una operación como suma, mínimo o máximo. Si solo hay unas pocas consultas sobre un arreglo pequeño, recorrer el intervalo directamente puede ser suficiente y requiere menos código.

Para sumas estáticas, elige Sumas de prefijos; para sumas con incrementos puntuales, Fenwick (BIT) suele requerir menos código y memoria. Si necesitas modificar un intervalo completo de forma eficiente, el siguiente paso es Segment tree con lazy propagation. Para práctica conjunta, consulta 20 - Fenwick y segment tree.