🧱 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:
| Índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| Valor | 3 | 1 | 4 | 2 | 5 | 0 | 2 | 1 |
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.
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ón | Ejemplo al consultar [2,6] | Acción para suma |
|---|---|---|
| No se tocan | nodo [0,1] | devolver 0 |
| El nodo queda completamente dentro | nodo [2,3] | devolver su resumen, 6 |
| Se superponen parcialmente | nodo [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:
- [0,7] se superpone parcialmente: consultamos [0,3] y [4,7].
- En [0,3], [0,1] queda fuera y devuelve 0; [2,3] queda completamente
dentro y devuelve 6. Esta mitad aporta
0 + 6 = 6. - En [4,7], [4,5] queda completamente dentro y devuelve 5. [6,7] se superpone parcialmente, así que bajamos una vez más.
- 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. - 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:
| Segmento | Suma anterior | Suma nueva |
|---|---|---|
| [4,4] | 5 | 8 |
| [4,5] | 5 | 8 |
| [4,7] | 8 | 11 |
| [0,7] | 18 | 21 |
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ón | Tiempo o espacio |
|---|---|
| Construir | O(n): se calcula cada nodo una vez |
| Asignar en una posición | O(log n) |
| Consultar un intervalo | O(log n) |
| Memoria | O(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 árbol | Intervalo que representa en este ejemplo | Suma 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 orden | Efecto |
|---|---|
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.
| Resumen | Combinar dos hijos | Respuesta de un segmento ajeno |
|---|---|---|
| Suma | x + y | 0 |
| Mínimo | min(x,y) | +∞ |
| Máximo | max(x,y) | −∞ |
| MCD | gcd(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.
¿Por qué devolver 0 fuera del rango rompe una consulta de mínimo?
Si el segmento incluido tiene mínimo 4 y el excluido devuelve 0, combinarlos produce
min(4,0) = 0: inventamos un valor que no estaba en el intervalo. Con +∞ obtenemosmin(4,+∞) = 4, que sí conserva la respuesta.
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.