🧱 Catálogo de estructuras

Una estructura de datos no se “corre” como un algoritmo: se construye y después se consulta muchas veces. Por eso lo que importa no es un costo total, sino el costo de cada operación — que es lo que compara esta tabla.

Elegir bien la estructura suele ser la mitad del problema: mira qué operaciones necesitas de verdad y toma la más barata que las cumpla todas.

Vienen en la librería estándar

De estas hay que saber usarlas: qué prometen y a qué costo. Están disponibles desde tu primer programa y la Ruta de Aprendizaje las introduce en los módulos 03, 06, 11 y 15. Las que la ruta no alcanza a usar —deque y las unordered_*— tienen aquí su ficha; de las unordered_* lee primero la advertencia de Complejidad computacional antes de preferirlas a set/map.

EstructuraOrigenTemaOperaciones principales
dequeSTLEstructuras de Datospush_back / push_front O(1) · pop_back / pop_front O(1) · d[i] O(1)
map (clave-valor)STLEstructuras de Datosm[clave] (leer o crear) O(log n) · count / find O(log n) · erase O(log n)
priority_queue (heap)STLEstructuras de Datospush O(log n) · pop O(log n) · top O(1)
set y multisetSTLEstructuras de Datosinsert O(log n) · find O(log n) · count(x) O(log n + k)
stack y queueSTLEstructuras de Datospush O(1) · pop O(1) · top (stack) / front (queue) O(1)
unordered_set y unordered_mapSTLEstructuras de Datosinsert / find / erase O(1) promedio · count O(1) promedio · Recorrer O(n)
vector (arreglo dinámico)STLEstructuras de Datosv[i] (acceso) O(1) · push_back O(1) amortizado · pop_back O(1)

Se implementan a mano

De estas hay que saber construirlas: son las que separan el nivel nacional del internacional. La ruta introduce DSU y consultas dinámicas en los módulos 19 y 20, y árboles en el 21. Sparse table, lazy propagation, el segment tree persistente y el trie amplían esas clases. Sus páginas traen la implementación de referencia.

EstructuraOrigenTemaOperaciones principales
DSU (Union-Find)a manoEstructuras de DatosCrear (n elementos) O(n) · find(x) O(α(n)) · unir(a, b) O(α(n))
Fenwick (BIT)a manoEstructuras de DatosConstruir desde n valores O(n log n) · Sumar delta en una posición O(log n) · Suma de prefijo [1..i] O(log n)
LCA con binary liftinga manoÁrbolesPrecálculo O(n log n) · LCA(u, v) O(log n) · Distancia entre dos nodos O(log n)
Segment treea manoEstructuras de DatosConstruir O(n) · Actualizar una posición O(log n) · Consultar un rango O(log n)
Segment tree con lazy propagationa manoEstructuras de DatosConstruir O(n) · Actualizar un RANGO O(log n) · Consultar un rango O(log n)
Segment tree persistentea manoEstructuras de DatosCrear una versión nueva O(log n) · Consultar cualquier versión O(log n) · Espacio total O(n + q log n)
Sparse table (RMQ)a manoEstructuras de DatosPrecálculo O(n log n) · Consultar mínimo/máximo de un rango O(1)
Sumas de prefijosa manoEstructuras de DatosConstruir los prefijos O(n) · Suma de un rango O(1) · Actualizar un valor O(n)
Triea manoStrings y SecuenciasInsertar una palabra O(largo) · Buscar una palabra O(largo) · Buscar un prefijo O(largo)

Cómo elegir

Necesito…Estructura
lista con acceso por posiciónvector
saber si algo ya aparecióset
contar cuántas veces aparece cada cosamap
sacar siempre el mayor o el menorpriority_queue
el vecino más cercano a un valorset (lower_bound)
sumas de rango sobre datos que no cambianSumas de prefijos
sumas de rango con actualizacionesFenwick (BIT)
mínimo/máximo de rango con actualizacionesSegment tree
actualizar rangos completosSegment tree con lazy propagation
mínimo/máximo de rango sin actualizacionesSparse table (RMQ)
juntar grupos que se van uniendoDSU (Union-Find)
buscar por prefijo de palabrasTrie

Referencias: Complejidad computacional (los costos en contexto) · Catálogo de algoritmos (la otra mitad del oficio) · Ruta de Aprendizaje (dónde se aprende cada una) · por tema: Temas · volver a Referencia.