5 października 2009
Zaawansowany: LCA i RMQ
Prowadzący: Paweł Lipski
Omówiłem dwa ciekawe problemy, dla których wymyślono mnóstwo rozwiązań. W pierwszym z nich LCA (Lowest Common Ancestor) musimy odpowiadać na zapytania: który wierzchołek jest najniższym (tj. najdalej położonym od korzenia) wspólnym przodkiem dwóch wierzchołków $u_i, v_i$ w danym drzewie $n$-wierzchołkowym? W RMQ (Range Minimum Query) natomiast dostaliśmy ciąg $A$ długości $m$ i pytamy się, który (dla danych $p_i, q_i: 1 \le p_i, q_i \le n$ element ciągu (jego indeks lub wartość) jest najmniejszy z elementów $A$ indeksach $j: p_i \le j \le q_i$.
Wszystkie algorytmy oprócz pierwszego (Tarjana dla LCA) są online, czyli na zapytania należy odpowiadać w natychmiast po jego otrzymaniu (nie otrzymamy kolejnego zapytania, zanim nie udzielimy odpowiedzi na bieżące). $I$ oznacza czas inicjalizacji algorytmu, a $Q$ - czas udzielenia odpowiedzi na zapytanie.
LCA (wszystkie rozwiązania prócz pierwszego online)
- Algorytm offline Tarjana (najpierw otrzymuje wszystkie zapytania, potem dopiero odpowiada), czas działania $o((n + q)\log^* n)$, gdzie $q$ jest liczbą zapytań. Korzysta ze struktury Find-Union (patrz wykład 28-09-2009).
- Algorytm z użyciem wyszukiwania binarnego: $I = O(n \log n), Q = O(\log n)$.
- Modyfikacja poprzedniego algorytmu z użyciem operacji na bitach: $I = O(n), Q = O(\log n)$.
RMQ (wszystkie rozwiązania online)
- Algorytm trywialny: $I = O(m^2), Q = O(1)$
- Rozwiązanie z użyciem kubełków pierwiastkowych: $I = O(m), Q = O(\sqrt m)$
- Rozwiązanie korzystające z drzew przedziałowych: $I = O(m), Q = O(\log m)$
- Algorytm używający przedziałów długości $2^i$ pokrywających wszystkie spójne podciągi: $I = O(m \log m), Q = O(1)$
Zadania domowe
- Komiwojażer Bajtazar, IX OI
- Problem: dany jest ciąg liczbowy $A$ długości $n, n \le 10^5$. Mamy odpowiadać na zapytania postaci $p_i, q_i$: czy w spójnym podciągu od $p$-tego do $q$-tego elementu znajduje się taka trójka liczb $a, b, c$, że nie mogą być one długościami boków trójkąta?
