Estructuras de datos

Elegir cómo guardar los datos decide si el programa tarda un segundo o una hora.

Armado con los posts publicados al 20 de septiembre de 2026.

Complejidad

Idea clave: Big O compara familias de crecimiento, no velocidades. Sirve para descartar lo que no puede escalar; las constantes se miden después, y sólo dentro de la familia que quedó.

Idea clave: El hash map no guarda los valores: guarda punteros a los nodos de la lista. Buscar la clave te da el nodo, y con el nodo en la mano moverlo al frente es reconectar cuatro punteros. Esa es toda la idea.
Idea clave: Hash map para encontrar, lista doblemente enlazada para ordenar por uso, y punteros compartidos entre las dos. El hash map guarda nodos, no valores; el nodo guarda su clave para poder borrarse del hash map cuando lo desaloja la cola. Con eso, get y put cuestan $O(1)$ promedio, y la caché usa $O(k)$ de memoria.

Idea clave: El «seguro que no» es exacto porque agregar sólo prende bits: si el elemento se hubiera agregado, sus $k$ posiciones estarían todas en uno. El «probablemente sí» es inexacto porque esas $k$ posiciones pueden haberse prendido por culpa de otros elementos.
Idea clave: El filtro de Bloom sirve cuando el costo de un falso positivo es una consulta de más y el costo de la memoria ahorrada es grande. Si el falso positivo hace perder un dato o negarle algo a una persona, el trato ya no es conveniente: ahí va la estructura exacta, o el filtro se usa sólo como primer paso y lo confirma la fuente de verdad.
Idea clave: Un arreglo de bits, $k$ hashes y una garantía asimétrica: el «no» es seguro y el «sí» es probable. Se elige la tasa de falso positivo y de ahí salen $m$ y $k$; cada orden de magnitud menos de error cuesta unos cinco bits por elemento. No se puede borrar ni agrandar, y sirve cuando equivocarse cuesta apenas una consulta de más.

Idea clave: Conviene que $P$ tenga un elemento más que $A$ y que $P[0]$ valga cero. Así el rango que empieza en la posición 0 no es un caso especial, y la mitad de los errores de índice de esta técnica desaparecen antes de existir.
Idea clave: Una pasada de $O(n)$ convierte cualquier consulta de suma por rango en una resta. Sirve cuando los datos casi no cambian; si cambian, cada modificación cuesta $O(n)$ y hace falta un Fenwick o un segment tree. El arreglo de diferencias es la misma idea al revés: modificar rangos en $O(1)$ y reconstruir una sola vez al final.

Idea clave: La diferencia clave está en la cuarta fila. Una suma se puede deshacer restando, y de eso vive el Fenwick. Un mínimo no: sacar un elemento de un conjunto no permite recuperar el mínimo de lo que queda. Para esas operaciones hace falta el segment tree, que guarda cada bloque completo.
Idea clave: Cuando los datos cambian tanto como se consultan, se guardan bloques en vez de totales. El Fenwick es un arreglo compacto que se mueve por el último bit encendido: quince líneas, sumas y otras operaciones invertibles. El segment tree guarda cada bloque completo, soporta cualquier operación asociativa y, con propagación diferida, también modificaciones por rango. Y si los datos no cambian, las sumas acumuladas siguen siendo mejores que los dos.

Idea clave: La técnica que las hace baratas se llama copia de camino: se copian sólo los nodos que hay entre la raíz y el punto modificado, y los nodos copiados apuntan a los hijos viejos, sin tocarlos. Es seguro justamente porque nadie modifica nada: un nodo compartido no puede cambiar bajo los pies de otra versión.
Idea clave: Una estructura persistente no copia: comparte. Cada modificación crea sólo el camino de la raíz al punto tocado —$O(\log n)$ nodos— y el resto queda compartido, lo que es seguro porque nada se escribe nunca. De ahí salen el deshacer barato, la comparación por identidad, la lectura sin candados entre hilos y los snapshots instantáneos. El precio es la indirección: no se elige por velocidad bruta.

atlas.matiascaliz.com.ar/materias/estructuras-de-datos — si algo de acá no se entiende solo, el post completo lo explica.