Pierwiastkowa dekompozycja zapytań

W niniejszym artykule chciałbym przedstawić Czytelnikom technikę, która może okazać się pomocna przy rozwiązywaniu różnych problemów informatycznych.

Rozważmy przykładowe zadanie. Dana jest $N$ -elementowa tablica $T$ liczb naturalnych z przedziału $) [0,N$ oraz $M$ zapytań postaci $(a,b),$ gdzie $.0⩽ a ⩽ b < N$ Dla każdego zapytania należy odpowiedzieć na pytanie ile różnych elementów ma podtablica $|T[a..b].$ Można łatwo napisać algorytm, który dla zapytania znajduje odpowiedź w czasie $), O(N$ a więc dla $M$ zapytań działa w czasie $M) O(N$ (kod źródłowy 1). Rozważmy jednak inne podejście do problemu. Zapamiętajmy wynik poprzedniego zapytania i spróbujmy zmodyfikować go tak, aby pasował do kolejnego (kod źródłowy 2).

Nasz algorytm wciąż rozwiązuje problem w czasie $M), O(N$ gdyż przejście z jednego zapytania do następnego może zająć $) O(N$ czasu. Jednak gdybyśmy zagwarantowali, że kolejne zapytania będą podobne, algorytm mógłby działać szybciej. Rozważmy problem, w którym znamy na wstępie wszystkie zapytania. Możemy wybrać kolejność w jakiej będziemy na nie odpowiadać. Załóżmy dla uproszczenia, że $|N$ jest kwadratem liczby naturalnej. Okazuje się, że istnieje kolejność, która gwarantuje, że nasz algorytm wykona jedynie $√ +N)N) O((M$ operacji.

Podzielmy przedział $) |[0, N$ na $√ -- | N$ części:

√ -- √ -- √ -- √ -- √ -- ). [0, N ),[ N ,2 N ),...,[( N −1) N ,N

Każdy z tych przedziałów jest rozmiaru $√ -- | N .$ Teraz utwórzmy kubełek dla każdego z nich. Dla każdego zapytania $(a,b)$ patrzymy do którego z tych kubełków wpada $|a$ i umieszczamy to zapytanie w odpowiednim kubełku. Następnie w każdym kubełku sortujemy zapytania rosnąco po wartościach $|b.$ Przeglądamy teraz kubełki po kolei i odpowiadamy na zapytania zgodnie z ustalonym porządkiem.

Obliczmy złożoność naszego algorytmu. Rozważmy dwie sytuacje. W pierwszej z nich oba zapytania należą do tego samego kubełka. W takiej sytuacji stare_a oraz a należą do tego samego przedziału. Nie wykonamy zatem więcej niż $O($ operacji dodaj i usuń w trakcie zmiany stare_a na a. Jeśli chodzi o wartości stare_b oraz b to są one w ramach jednego kubełka posortowane rosnąco. Oznacza to, że jeśli dwa zapytania są w jednym kubełku, to będziemy wykonywać jedynie operację dodaj. A więc dla ustalonego kubełka sumarycznie wystarczy wykonać jedynie $) O(N$ takich operacji przy zmianach stare_b na b. Rozważmy teraz sytuację w której zapytania należą do różnych kubełków. Jak powiedzieliśmy wcześniej, w najgorszym przypadku wykonamy $) O(N$ operacji między dwoma zapytaniami. Jednak taka sytuacja zdarzy się co najwyżej $|O($ razy, bo tylko tyle mamy kubełków. A więc sumarycznie nasz algorytm zadziała w czasie

√N+N√N+N√N)=O((M+N)√N). O(M

A teraz dwa ćwiczenia dla Drogiego Czytelnika. Pierwsze jest następujące: mając daną tablicę $| −1] T [0..N$ oraz $| M$ zapytań $| (a,b)$ należy dla każdego zapytania odpowiedzieć ile inwersji znajduje się w podtablicy $|T[a..b].$ Inwersją w tablicy $T$ nazywamy taką parę liczb $(i, j),$ że $i < j$ oraz $|T[i] > T [ j].$ Drugie zaś brzmi: mając dany graf $=(V,E) G$ oraz tablicę jego krawędzi $| T ,$ należy dla każdego zapytania $| (a,b)$ odpowiedzieć na pytanie ile spójnych składowych ma graf obcięty do krawędzi $T [a..b].$ Każde z tych zadań można rozwiązać za pomocą opisanej w artykule techniki, nazywanej pierwiastkową dekompozycją zapytań, jednakże wymagają one dodatkowego pomysłu. Mam nadzieję, że rozwiązywanie tych zadań przyniesie Czytelnikom dużo frajdy.