Dla zawodników

W tym artykule opowiem nieco o zupełnie odmiennym od standardowego podejściu do tworzenia struktur danych ─ strukturach trwałych, a także przedstawię implementacje kilku najpopularniejszych struktur ─ stosów, drzew wyszukiwań binarnych i kolejek ─ w wersji trwałej.

W tym artykule prezentuję rozwiązania trzech zadań ze SPOJa. Wszystkie pochodzą z (dość długiego) cyklu "Answer these queries" i (mimo dość podobnie wyglądających sformułowań) wymagają połączenia kilku różnych, i to dość nietrywialnych, pomysłów. Ze względu na zróżnicowany poziom trudności lekturę polecam zarówno początkującym, jak i starym wyjadaczom.

Każdy może czasem potrzebować k-tego elementu w n-wierzchołkowym drzewie. Przedstawimy kilka sposobów, mniej lub bardziej efektywnych, jak go znaleźć. Po drodze dowiemy się dlaczego STL wcale nie jest taki fajny, jak szukać mediany i że oszczędzanie połowy pracy na każdej operacji daje świetne efekty.

Pomocna w rozwiązaniu wielu problemów algorytmicznych z gatunku programowania dynamicznego bywa  umiejętność zwięzłego zapisu wszystkich możliwych do osiągnięcia stanów. Spotykamy problemy, w których te stany to pewne podzbiory. Co to oznacza? W jaki sposób reprezentować podzbiory i czy faktycznie jest to dobry i skuteczny sposób rozwiązywania problemów algorytmicznych? Odpowiedzi na te pytania znajdziesz w tym artykule.