Informatyczny kącik olimpijski

Słownik przekątnych

W tym odcinku zajmiemy się zadaniem, które zamiast na zawodach, pojawiło się na... kolokwium (z Algorytmów i Struktur Danych). Stanowiłoby ono bardzo ładne zadanie na zawodach.

Rys. 1 Kilka przekątnych ośmiokąta reprezentowanych jako łuki. Wartością $\text{[math]}$ jest łuk $\text{[math]}$

Od czego zacząć? Na początek może ułatwimy sobie zadanie — zauważmy, że wielokąt z zadania można „wygiąć” na płaszczyźnie, aż wierzchołki utworzą ciąg punktów na prostej, ponumerowanych od $\text{[math]}$ do $\text{[math]}$ , a przekątne zamienią się na łuki (jak na rysunku 1). Resztę zadania łatwo przetłumaczyć do tej nowej wersji. W tym momencie już pojawia się pomysł — może uda się użyć drzewa przedziałowego? Ale zanim napiszemy jak, wyjaśnijmy sobie, co będziemy rozumieć przez drzewo przedziałowe.

Drzewo przedziałowe (rys. 2) służy do przechowywania informacji związanych z podprzedziałami zadanego przedziału $\text{[math]}$ . W korzeniu drzewa jest zapisana informacja związana z całym przedziałem, w jego dwóch synach informacje związane z lewą i prawą połową tego przedziału i tak dalej, aż wreszcie w liściach zapamiętywane są wartości odpowiadające pojedynczym punktom. Wartość przechowywaną w wierzchołku $\text{[math]}$ będziemy oznaczać $\text{[math]}$

Jako ćwiczenie Czytelnik może w oparciu o drzewo przedziałowe skonstruować strukturę danych do obsługi dynamicznie zmieniającego się ciągu $\text{[math]}$ , dopuszczającą operacje (1) inicjuj wszystkie wyrazy na $\text{[math]}$ , (2) ustaw $\text{[math]}$ oraz (3) podaj sumę podciągu $\text{[math]}$ . Operacje (2) i (3) powinny działać w czasie $\text{[math]}$ .

No dobrze, ale jak to zastosować do naszego problemu?

Zapytajmy, kiedy w nowym modelu (tym z prostą), można połączyć dwa punkty $\text{[math]}$ i $\text{[math]}$ przekątną? Spójrzmy na rysunek 1. Dla danego $\text{[math]}$ niech $\text{[math]}$ oznacza najniższy łuk, który przecina pionowa półprosta wychodząca z punktu $\text{[math]}$ (dotknięcie nie liczy się jako przecięcie; wartością $\text{[math]}$ może być „pusty” łuk). Łuk od $\text{[math]}$ do $\text{[math]}$ można dodać dokładnie wtedy, gdy $\text{[math]}$ . Musimy więc szybko obliczać wartości funkcji $\text{[math]}$ . Do tego przyda się drzewo przedziałowe.

Przypuśćmy, że wiemy już, iż możemy dodać przekątną $\text{[math]}$ . Jak to zrobić? Otóż przekątna „pokryje” podciąg wierzchołków $\text{[math]}$ . Słowo pokryje oznacza, że półprosta wychodząca z każdego z wierzchołków z tego przedziału przetnie naszą przekątną, choć niekoniecznie jako pierwszą.

Funkcja dodająca przekątną $\text{[math]}$ będzie działać rekurencyjnie. Najpierw wywołujemy ją dla korzenia. Dodając przekątną $\text{[math]}$ w wierzchołku $\text{[math]}$ drzewa przedziałowego, wykonujemy operacje:

•: jeśli podprzedział z wierzchołka $\text{[math]}$ zawiera się w $\text{[math]}$ , to ustaw $\text{[math]}$ na niższy z łuków $\text{[math]}$ i $\text{[math]}$ (wysokość łuku można szybko obliczyć, jest to $\text{[math]}$ ),
•: jeśli podprzedział z wierzchołka $\text{[math]}$ jest rozłączny z $\text{[math]}$ , to nic nie rób,
•: w przeciwnym razie wywołaj funkcję $\text{[math]}$ dla dzieci wierzchołka $\text{[math]}$

Łatwo zauważyć, że $\text{[math]}$ to najniższy spośród łuków zapamiętanych w wierzchołkach drzewa odpowiadających przedziałom pokrywającym punkt $\text{[math]}$ , czyli na ścieżce prowadzącej z korzenia do wierzchołka $\text{[math]}$ . Zatem $\text{[math]}$ można znaleźć w czasie $\text{[math]}$ .

Funkcja Sprawdź może działać na podobnej zasadzie, sprawdzając, czy w odwiedzanych po drodze wierzchołkach jest zapamiętana poszukiwana przekątna. (Każda wstawiona przekątna zostaje gdzieś zapamiętana, dlaczego?)

Aktualizację stanu struktury podczas usuwania przekątnej pozostawiamy Czytelnikowi.