05.10.2009

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?