Estructuras de Datos
Segment/Fenwick tree, DSU, sparse table, prefix sums.
Volver a los 11 temas · Referencia · temarios: Syllabus OCI · Syllabus IOI.
📍 Clases relacionadas: módulos 03 · 06 · 11 · 17 · 19 · 20 de la Ruta de Aprendizaje.
📋 En el temario OCI: desde la Regional: arreglos, matrices y vector (♡); set, map y priority_queue como cajas negras (⊖).
Una estructura de datos guarda información de manera que ciertas preguntas se respondan rápido. Elegir la correcta suele ser la mitad del problema; la otra mitad es darse cuenta de qué pregunta hay que hacerle.
📌 Qué abarca
- Stacks / colas (incl. monótonos), heap binario.
- DSU (Union-Find) con compresión de caminos y unión por tamaño/rango.
- Fenwick (BIT) y segment tree (suma/mín/máx, lazy propagation).
- Sparse table / RMQ; compresión de coordenadas; prefix sums.
- BBST (árbol binario de búsqueda balanceado: lo que hay dentro de
setymap) balanceado y aumentado; segment tree persistente; Li Chao (su página vive en Programación Dinámica, porque su uso es optimizar DP). - Anidamiento de estructuras (p.ej. segment tree de conjuntos); tries.
- Análisis amortizado.
⛔ Fuera del syllabus IOI
- Tablas hash: lo excluido es implementarlas y razonar sobre colisiones —
usar
unordered_mapes perfectamente legal (ver unordered_set y unordered_map y su trampa anti-hash). - Estructuras 2D (BIT 2D, treap de treaps).
- Heaps de Fibonacci / binomiales; link-cut / árboles dinámicos.
- Persistencia por fat-nodes (basta path-copying).
Los problemas no distinguen qué BBST uses (treap, splay, AVL, scapegoat son equivalentes).
🎯 En competencia
En la OCI — En la Regional se trata de usar bien lo básico: arreglos, matrices, vector, y desde el techo avanzado set, map y priority_queue sin saber cómo funcionan por dentro. Nada de implementar estructuras: Fenwick, segment tree y DSU son material del campamento. En este vault hay 16 problemas OCI del tema (8 de fases regionales, 7 de fases nacionales y 1 de clasificatorias IOI); están en la tabla de abajo.
En la IOI — Fenwick y segment tree son omnipresentes; DSU resuelve conectividad offline (procesar consultas ordenadas). Ver Búsqueda Binaria para “descenso” sobre el árbol.
⚠️ La trampa típica
Mezclar indexación desde 0 y desde 1 dentro de la misma solución (clásico con Fenwick), y usar map donde un vector bastaba: mismo O(log n) en el papel, varias veces más lento en la práctica.
🧱 Estructuras de datos
De la librería estándar — hay que saber usarlas:
- deque
- map (clave-valor)
- priority_queue (heap)
- set y multiset
- stack y queue
- unordered_set y unordered_map
- vector (arreglo dinámico)
Se implementan a mano — hay que saber construirlas:
- DSU (Union-Find)
- Fenwick (BIT)
- Segment tree
- Segment tree con lazy propagation
- Segment tree persistente
- Sparse table (RMQ)
- Sumas de prefijos
Todas juntas y comparables en el Catálogo de estructuras.
⚙️ Algoritmos y técnicas
🇨🇱 Problemas OCI (en español)
Empieza por acá: son problemas oficiales chilenos, con enunciado en español y mirror para enviar. Consulta la orientación de estudio al comienzo de esta página. La dificultad orienta la elección, pero no garantiza una solución completa.
| Problema | Competencia | Dificultad |
|---|---|---|
| Sistemas interestelares | 2015 Nacional | 🟢 fácil |
| Cuenta de goles | 2025 Regional | 🟢 fácil |
| Fórmula 1 | 2019 Nacional | 🟢 fácil |
| Escaleras y Serpientes | 2018 Nacional | 🟡 media |
| El lokómon de Olivier | 2022 Regional | 🟡 media |
| Reuniones | 2019 Regional | 🟡 media |
| Tranvía en Chuchunco | 2024 Regional | 🟡 media |
| Las mejores peores películas | 2025 Nacional | 🟡 media |
| Cine | 2024 Nacional | 🟡 media |
| Ocimatic | 2016 Regional | 🔴 difícil |
| Ca-chi-pún | 2017 Clasificatoria | 🔴 difícil |
| Problema Presidencial: Paltas Promedio | 2019 Regional | 🔴 difícil |
| El lokómon legendario | 2020 Regional | 🔴 difícil |
| Roberto el constructor | 2020 Nacional | 🔴 difícil |
| Apuesta de alto riesgo | 2024 Regional | 🔴 difícil |
| Aplausómetro | 2024 Nacional | 🔴 difícil |
🌍 Problemas IOI
De más abordable a más duro, según el puntaje promedio que sacaron los competidores: una media alta sugiere más puntos parciales accesibles, no más soluciones completas. Consulta también el porcentaje de 100 y los prerrequisitos.
| Problema | Año | Media (puntos parciales) | Lograron 100 |
|---|---|---|---|
| Mutating DNA | 2021 | 93/100 | 86% |
| Connecting Supertrees | 2020 | 78/100 | 44% |
| Arranging Shoes | 2019 | 74/100 | 52% |
| Nile | 2024 | 68/100 | 35% |
| Mosaic | 2024 | 59/100 | 25% |
| Horses | 2015 | 51/100 | 36% |
| Overtaking | 2023 | 45/100 | 8% |
| Obstacles for a Llama | 2025 | 45/100 | 3% |
| Triple Peaks | 2025 | 43/100 | <1% |
| Rectangles | 2019 | 37/100 | 7% |
| Catfish Farm | 2022 | 34/100 | 14% |
| Keys | 2021 | 31/100 | 5% |
| Werewolf | 2018 | 31/100 | 5% |
| Dungeons Game | 2021 | 30/100 | 4% |
| Roller Coaster Railroad | 2016 | 26/100 | 1% |
| Digital Circuit | 2022 | 25/100 | 15% |
| Teams | 2015 | 23/100 | 4% |
| Meetings | 2018 | 22/100 | 0% |
| Distributing Candies | 2021 | 21/100 | 7% |
| Monuments | 2026 | 20/100 | <1% |
| Radio Towers | 2022 | 19/100 | 2% |
| Tree | 2024 | 18/100 | 1% |
| Comparing Plants | 2020 | 15/100 | 3% |
| Seats | 2018 | 14/100 | <1% |
| Sky Walking | 2019 | 13/100 | <1% |