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 set y map) 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_map es 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:

Se implementan a mano — hay que saber construirlas:

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.

ProblemaCompetenciaDificultad
Sistemas interestelares2015 Nacional🟢 fácil
Cuenta de goles2025 Regional🟢 fácil
Fórmula 12019 Nacional🟢 fácil
Escaleras y Serpientes2018 Nacional🟡 media
El lokómon de Olivier2022 Regional🟡 media
Reuniones2019 Regional🟡 media
Tranvía en Chuchunco2024 Regional🟡 media
Las mejores peores películas2025 Nacional🟡 media
Cine2024 Nacional🟡 media
Ocimatic2016 Regional🔴 difícil
Ca-chi-pún2017 Clasificatoria🔴 difícil
Problema Presidencial: Paltas Promedio2019 Regional🔴 difícil
El lokómon legendario2020 Regional🔴 difícil
Roberto el constructor2020 Nacional🔴 difícil
Apuesta de alto riesgo2024 Regional🔴 difícil
Aplausómetro2024 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.

ProblemaAñoMedia (puntos parciales)Lograron 100
Mutating DNA202193/10086%
Connecting Supertrees202078/10044%
Arranging Shoes201974/10052%
Nile202468/10035%
Mosaic202459/10025%
Horses201551/10036%
Overtaking202345/1008%
Obstacles for a Llama202545/1003%
Triple Peaks202543/100<1%
Rectangles201937/1007%
Catfish Farm202234/10014%
Keys202131/1005%
Werewolf201831/1005%
Dungeons Game202130/1004%
Roller Coaster Railroad201626/1001%
Digital Circuit202225/10015%
Teams201523/1004%
Meetings201822/1000%
Distributing Candies202121/1007%
Monuments202620/100<1%
Radio Towers202219/1002%
Tree202418/1001%
Comparing Plants202015/1003%
Seats201814/100<1%
Sky Walking201913/100<1%