Algorytmy i struktury danych · Senior · Pytanie 71 z 75
Na co odpowiada w O(1) struktura „sparse table”?
- ✓Poprawna odpowiedź: Zapytania o minimum na zakresie niezmiennej tablicy
- 2Sprawdzanie przynależności w dynamicznym zbiorze kluczy
- 3Najkrótsze ścieżki między dowolnymi dwoma wierzchołkami
Wyjaśnienie
Z góry liczy minima wszystkich zakresów długości 2ᵏ w O(n log n). Każdy zakres pokrywają dwa nakładające się zakresy o długości potęgi dwójki, a dla min nakładanie się nie ma znaczenia. Aktualizacje wymagałyby przebudowy.