🧱 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.
| Estructura | Origen | Tema | Operaciones principales |
|---|---|---|---|
| deque | STL | Estructuras de Datos | push_back / push_front O(1) · pop_back / pop_front O(1) · d[i] O(1) |
| map (clave-valor) | STL | Estructuras de Datos | m[clave] (leer o crear) O(log n) · count / find O(log n) · erase O(log n) |
| priority_queue (heap) | STL | Estructuras de Datos | push O(log n) · pop O(log n) · top O(1) |
| set y multiset | STL | Estructuras de Datos | insert O(log n) · find O(log n) · count(x) O(log n + k) |
| stack y queue | STL | Estructuras de Datos | push O(1) · pop O(1) · top (stack) / front (queue) O(1) |
| unordered_set y unordered_map | STL | Estructuras de Datos | insert / find / erase O(1) promedio · count O(1) promedio · Recorrer O(n) |
| vector (arreglo dinámico) | STL | Estructuras de Datos | v[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.
| Estructura | Origen | Tema | Operaciones principales |
|---|---|---|---|
| DSU (Union-Find) | a mano | Estructuras de Datos | Crear (n elementos) O(n) · find(x) O(α(n)) · unir(a, b) O(α(n)) |
| Fenwick (BIT) | a mano | Estructuras de Datos | Construir 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 lifting | a mano | Árboles | Precálculo O(n log n) · LCA(u, v) O(log n) · Distancia entre dos nodos O(log n) |
| Segment tree | a mano | Estructuras de Datos | Construir O(n) · Actualizar una posición O(log n) · Consultar un rango O(log n) |
| Segment tree con lazy propagation | a mano | Estructuras de Datos | Construir O(n) · Actualizar un RANGO O(log n) · Consultar un rango O(log n) |
| Segment tree persistente | a mano | Estructuras de Datos | Crear 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 mano | Estructuras de Datos | Precálculo O(n log n) · Consultar mínimo/máximo de un rango O(1) |
| Sumas de prefijos | a mano | Estructuras de Datos | Construir los prefijos O(n) · Suma de un rango O(1) · Actualizar un valor O(n) |
| Trie | a mano | Strings y Secuencias | Insertar una palabra O(largo) · Buscar una palabra O(largo) · Buscar un prefijo O(largo) |
Cómo elegir
| Necesito… | Estructura |
|---|---|
| lista con acceso por posición | vector |
| saber si algo ya apareció | set |
| contar cuántas veces aparece cada cosa | map |
| sacar siempre el mayor o el menor | priority_queue |
| el vecino más cercano a un valor | set (lower_bound) |
| sumas de rango sobre datos que no cambian | Sumas de prefijos |
| sumas de rango con actualizaciones | Fenwick (BIT) |
| mínimo/máximo de rango con actualizaciones | Segment tree |
| actualizar rangos completos | Segment tree con lazy propagation |
| mínimo/máximo de rango sin actualizaciones | Sparse table (RMQ) |
| juntar grupos que se van uniendo | DSU (Union-Find) |
| buscar por prefijo de palabras | Trie |
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.