LCA, bardzo dobre źródło nauki

pytanie zadane 8 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Pozwolę sobie umieścic linka, do świetnego omówienia LCA(jak ktoś się chce nauczyć LCA, to idealnie), artykułu Pana Radoszewskiego, opisuje w około 4 minuty, jak napisać LCA, moim zdaniem w bardzo przystępny sposób. Polecam najpierw przeczytać wprowadzenie o co chodzi, potem od RMQ do LCA radziłbym ominąć na początek, opisuje tam bardzo dziwne rzeczy, ale bardzo przystępne i stosunkowo nietrudne jest opis od LCA do RMQ. Wystarczy się puścić zwykłym DFS-em preorder, napełnić drzewo przedziałowe i w O(lg N) odpowiadać na zapytania.

Link: https://www.mimuw.edu.pl/~rytter/TEACHING/JAO/radoszwski_delta.pdf

Wydaje się być to jakiś wpis z delty, ale nie jestem pewien.

komentarz 8 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

i tu jest też fajne zadanie na LCA z 1 etapu IX OI: https://szkopul.edu.pl/problemset/problem/-fb7NxSJGXxkJ2Om5FvXzbil/site/?key=statement

komentarz 8 kwietnia 2023 przez Whistleroosh Maniak (56,980 p.)

Ja wolałem zawsze implementować LCA za pomocą binary lifting. Kod jest chyba trochę prostszy

komentarz 8 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Ale co ciekawe tym jego sposobem można chyba zrobić w czasie liniowym preprocesing i w czasie stałym odpowiadać na zapytania, jeśli zaimplementujemy sparse table liniowo(chyba się da), więc LCA też chyba jedzie działać w czasie stałym.

komentarz 8 kwietnia 2023 przez Whistleroosh Maniak (56,980 p.)

Da się zrobić sparse table liniowo? Jeśli dobrze pamiętam jak to działa to trzeba policzyć nlogn wartości, więc szybciej niż O(nlogn) się tego nie zrobi.

komentarz 8 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Właśnie wydaje mi się, że obiło mi się o uszy, że się jakoś da, tylko nwm jak, bo to klasyczne to wiadomo, przedziały długości logarytm, a liniowo to nwm jak to miało by wyglądać wsm.

komentarz 8 kwietnia 2023 przez Whistleroosh Maniak (56,980 p.)

Moim zdaniem się nie da. To w słowniku podsłów bazowych (czyli w zasadzie takim sparse table) dało się zbić złożoność do O(nlogn) przez sortowanie liniowe na kazdym z poziomów. Ale całości liniowo nie da się policzyć

komentarz 30 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@Whistleroosh,

Pełna zgoda, binary lifting zdecydowanie lepszy, trochę mi to zajęło, żeby zrozumieć czemu, ale problem jest taki, że te drzewko przedziałowe, to znajdzie ci LCA i gdy chcemy znaleźć długość ścieżki pomiędzy dwoma wierzchołkami to zadziała, bo naliczymy dla każdego wierzchołka glebokosc do korzenia, ale gdy chcemy znać min-a na ścieżce to chyba stypa...