Załóżmy na chwilę, że jeżeli musimy odpowiedzieć na zapytanie dla wierzchołka q1, to na ścieżce z q1 do korzenia drzewa nie ma już żadnych zapytań. W takim wypadku powyższy algorytm nigdy nie przetworzy jednego wierzchołka dwa razy (ponieważ ten sam wierzchołek nigdy nie występuje w poddrzewach dwóch różnych zapytań). Zatem ilość wykonywanych operacji to tylko O(n log n)! Jasno widać zatem słabość naszego rozwiązania – jeżeli odpowiedzieliśmy na zapytanie w wierzchołku v oraz istnieje zapytanie o poddrzewo wierzchołka u, który leży gdzieś na ścieżce z v do korzenia, to odpowiadając na zapytanie w u wierzchołki z poddrzewa v przetworzymy ponownie.
Potrzebna byłaby struktura danych przechowująca zbiór elementów, umożliwiająca wybieranie k-tego z nich oraz dodawanie nowych. Używając jej moglibyśmy odpowiadać na zapytania w kolejności ich występowania w drzewie. Odpowiadając na zapytanie w wierzchołku v zaczęlibyśmy od przetworzenia wszystkich poddrzew v (rysunek po lewej). Otrzymane w ten sposób zbiory elementów w poddrzewach połączylibyśmy w nowy zbiór i dodali przetwarzany wierzchołek v (rysunek po prawej). W ten sposób powstałby zbiór wszystkich wierzchołków poddrzewa v, z którego dałoby się szybko wyciągnąć k-ty element. Zadowalająca nas struktura danych to na przykład drzewa czerwono-czarne. Oczywiście ich najsilniejszym atutem jest to, że nie trzeba ich implementować – gotową (i działającą!) implementacją jest bowiem struktura set<> z biblioteki STL. Żeby jednak nie było zbyt pięknie trzeba dodać, że owa implementacja nie umożliwia szybkiego wybierania k-tego elementu (chociaż jest to możliwe z wykorzystaniem drzew czerwono-czarnych). Można pokusić się o zaimplementowanie drzew AVL – jest to prostsza struktura danych o podobnych możliwościach. Okazuje się jednak, że do naszych celów wystarczające będą zwykłe drzewa licznikowe.
Drzewo licznikowe to zrównoważone drzewo binarne. W jego liściach pamiętamy elementy, które mogą znaleźć się w przechowywanym zbiorze (to znaczy nie tylko te, które już dodaliśmy – musimy zrobić miejsce dla wszystkich elementów, które kiedykolwiek zechcemy dodać), w kolejności posortowanej (to znaczy najmniejszy element będzie w pierwszym liściu, a największy w ostatnim). W pozostałych wierzchołkach pamiętamy, ile elementów jest w ich poddrzewach. Dodawanie elementu jest proste: mamy już zarezerwowane miejsce na element, zatem wystarczy oznaczyć je jako "zajęte" oraz przejść ścieżką do korzenia zwiększając liczniki w każdym wierzchołku. Jeżeli drzewo może pamiętać n elementów, operacja ta potrwa O(log n), ponieważ tyle właśnie pięter drzewa dzieli liście od korzenia. Wyszukiwanie k-tego element również jest proste. Rozpoczynamy z korzenia i spoglądamy na lewego i prawego syna. Każdy z nich pamięta, ile elementów jest w jego poddrzewie (niech będą to odpowiednio a oraz b). Co więcej, wszystkie elementy z poddrzewa lewego syna są mniejsze od elementów z poddrzewa prawego syna. Zatem jeżeli zachodzi k < a, to szukany element z pewnością znajduje się w poddrzewie lewego syna. W przeciwnym wypadku poszukujemy (k-a)-tego elementu w poddrzewie prawego syna. W powyższych rachunkach wygodnie jest, aby k=0 oznaczało najmniejszy element oraz aby drzewo było pełne, tzn. ilość jego liści była potęgą dwójki. Jak widać wykonujemy tylko jedną operację na każdy poziom drzewa, zatem wyszukiwanie k-tego elementu również trwa O(log n).
Uzbrojeni w tak wspaniałe narzędzia powróćmy do zadania. Jakie elementy chcielibyśmy pamiętać w drzewie licznikowym? Prawdopodobnie pary (etykieta,wierzchołek). Ponieważ porównujemy takie pary tylko po etykietach, wystarczy zarezerwować w drzewie jednego liścia dla każdej możliwej etykiety. Aby nie było zbyt wspaniale przypominamy, że mogą one być dowolnie duże (no dobrze, powiedzmy że z zakresu -1.000.000.000 do +1.000.000.000). Czy to przekreśla nasze rozwiązanie?
Na szczęście nie. Uratuje nas fakt, że wprawdzie etykiety są duże, ale jest ich niewiele (przynajmniej nie więcej niż wierzchołków drzewa). Możemy zatem stworzyć izomorfizm miedzy etykietami a liczbami z zakresu 1 ... n (gdzie n jest ilością możliwych etykiet). Kluczową obserwacją jest to, że nie interesuje nas wartość etykiety (na przykład 214.042), a jedynie jej pozycja względem innych etykiet (czyli 214.042 < 324.441). Spróbujmy przenumerować etykiety tak, aby relacja mniejszości została zachowana, a liczby, którymi operujemy, były mniejsze. W tym celu wystarczy na początku programu posortować wszystkie etykiety. Następnie najmniejszą etykietę zamienić na 1, kolejną na 2, następną na 3 i tak dalej. Jeżeli będziemy jedynie porównywać etykiety między sobą, nigdy nie zorientujemy się, co się stało. Koszt całej maskarady to tylko O(n log n) na początku programu, a zatem całkiem nieźle.
Przyjrzyjmy się jeszcze rozmiarowi drzewa licznikowego. Będzie ono miało n liści, zatem wszystkich wierzchołków 2n-1. Przypomnijmy algorytm: rozpatrując wierzchołek v, tworzymy zbiory wierzchołków dla wszystkich poddrzew, każdy taki zbiór reprezentując jako drzewo licznikowe. Niestety poddrzew tych może być dużo (nawet rzędu n), zatem złożoność pamięciowa tego kroku byłaby O(n · (2n-1)) – za dużo. Chcielibyśmy, aby drzewo licznikowe zużywało pamięć tylko, kiedy jest to rzeczywiście niezbędne, czyli aby jego rozmiar rósł proporcjonalnie względem ilości elementów, które przechowuje. Suma mocy poddrzew nigdy nie przekroczy ilości wierzchołków w całym drzewie, zatem suma rozmiarów drzew licznikowych również byłaby pod kontrolą. Po połączeniu drzew licznikowych moglibyśmy usunąć oryginały (nie będą już potrzebne), dzięki czemu ilość zużywanej pamięci w każdym momencie byłaby O(n). Rzeczywiście można zaimplementować takie "pływające" drzewo licznikowe. Idea polega na tym, aby nie tworzyć wszystkich wierzchołków i liści na starcie, lecz w miarę dodawania nowych elementów. Zauważmy, że nie przeczy to pomysłowi zarezerwowania każdemu możliwemu elementowi miejsca w drzewie. Doskonale wiemy, gdzie ma wylądować każdy element – po prostu nie alokujemy dla niego pamięci, dopóki nie jest ona potrzebna, czyli pamiętamy tylko tą istotną (niepustą) część drzewa. Rysunek obok przedstawia drzewo licznikowe poprzedniego przykładu w wersji "pływającej". Linią przerywaną zaznaczono wierzchołki, dla których nie rezerwujemy pamięci.
Ostatnią trudnością jest sposób łączenia drzew licznikowych. Łatwo jest w czasie liniowym wyciągnąć wszystkie elementy drzewa licznikowego. Gdybyśmy jednak utworzyli nowe drzewo licznikowe i wrzucali do niego kolejne znajdowane elementy ze wszystkich poddrzew, ilość wykonywanych operacji byłaby zbyt duża (na przykład dla drzewa na rysunku obok). Na szczęście nie musimy tworzyć nowego drzewa licznikowego. Zamiast tego będziemy sklejać dwa drzewa kopiując elementy z mniejszego do większego (rozmiary drzew znamy – są zapisane w korzeniach). Następnie mniejsze drzewo wyrzucimy, a większe drzewo połączymy z kolejnym w ten sam sposób. Dzięki temu jeden element będzie kopiowany do nowego drzewa co najwyżej log n razy (prześledź losy jednego elementu i zastanów się, jak zmieniają się rozmiary drzewa, w którym się znajduje), zatem ilość wszystkich operacji, jakie wykonamy odpowiadając na wszystkie zapytania będzie O(n log n log n) (pamiętamy, że dodawanie elementu do drzewa licznikowego trwa O(log n); zauważ, że złożoność opisanego algorytmu nie zależy od ilości zapytań).
W ten sposób otrzymujemy rozwiązanie o złożoności czasowej O(n log2n + q log n) oraz liniowej złożoności pamięciowej. Jest ono niestety dość skomplikowane i raczej nieprzyjemne w implementacji. W dalszej części przedstawimy rozwiązanie zdecydowanie ciekawsze.
Jedną ze znanych operacji, jakie można wykonać na drzewie, jest przekształcenie go do odcinka, to znaczy wypisanie wszystkich wierzchołków w porządku pre-order lub post-order. Jeżeli potraktowalibyśmy nasze drzewo w ten sposób, problem znalezienia k-tego elementu w poddrzewie v sprowadza się do problemu znalezienia k-tego elementu na pewnym pod-odcinku (ponieważ każde poddrzewo w porządku pre-order jest spójnym odcinkiem). Zamienienie drzewa na odcinek oraz wyznaczenie zakresów pod-odcinków (tzn. gdzie zaczyna się, a gdzie kończy zapis każdego poddrzewa) jest proste.
Gdybyśmy mieli odpowiadać na wiele zapytań postaci "znajdź k-ty elementy na odcinku", moglibyśmy użyć opisanego wcześniej drzewa licznikowego. Musimy jednak udoskonalić to rozwiązanie, aby móc również znajdować k-ty element na pod-odcinkach. W tym celu w korzeniu naszego drzewa zapamiętamy numery wszystkich elementów z odcinka (dokładnie w takiej kolejności, w jakiej występują na odcinku – czyli po prostu 0,1,2,...,n-1). Następnie w lewym synu zapamiętamy numery elementów mniejszych od mediany, a w prawym większych od mediany (wciąż w takiej kolejności, jak na odcinku). Dzięki temu lewy i prawy syn będą zawierali po połowie elementów ojca oraz wszystkie elementy z lewego syna będą mniejsze od elementów z prawego – podobnie jak w drzewie licznikowym. Oczywiście będziemy dzielić w ten sposób rekurencyjnie, aż dojdziemy do zbiorów jednoelementowych. Zauważmy, że każdy element będzie pamiętany tylko w log n "kubełkach", zatem rozmiar całego drzewa będzie O(n log n). Podzielnie jednego kubełka na dwa wymaga O(n) operacji, ponieważ medianę potrafimy znaleźć w czasie liniowym, dalej zaś wystarczy przejrzeć wszystkie elementy z kubełka i dodać je do lewego lub prawego, w zależności od tego czy są mniejsze czy większe od znalezionej mediany (ważne jest, aby w kubełkach zachować kolejność taką, jak na odcinku). Zatem zbudowanie całego drzewa będzie wymagało czasu proporcjonalnego do jego rozmiaru, czyli również O(n log n).
Konstrukcję struktury dla przykładowego odcinka przedstawia rysunek powyżej. W pierwszym kubełku zapamiętujemy indeksy wszystkich elementów odcinka. Medianą wartości na odcinku jest 2 (zaznaczona na czerwono), zatem w lewym kubełku znajdą się indeksy elementów mniejszych od 2, w prawym zaś pozostałe. Gruba linia podziału oznacza, że dokonujemy podziału kubełka, cienka że dokonaliśmy podziału wcześniej. Zauważ, że indeksy w jednoelementowych kubełkach na samym dole odpowiadają posortowanemu ciągowi wyjściowemu.
Jak przy użyciu takiej struktury znaleźć k-ty element na pod-odcinku? W korzeniu pamiętamy wprawdzie cały odcinek, ale używając wyszukiwania binarnego możemy prosto znaleźć przedział, który zawiera tylko elementy z interesującego nas pod-odcinka (ponieważ pamiętamy numery elementów, a nie ich wartości). Gdybyśmy zatem w myślach znaleźli takie przedziały w każdym kubełku i zapomnieli o tym, że są tam również inne elementy, nasza struktura okazałaby się drzewem licznikowym dla pod-odcinka. W takim zaś znaleźć k-ty element już potrafimy. Na rysunku powyżej kolorem niebieskim zaznaczono we wszystkich kubełkach przedziały, które odpowiadają przykładowemu pod-odcinkowi. Koszt pojedynczego wyszukiwania to O(log n log n) ponieważ postępujemy tak samo jak dla drzewa licznikowego z tym, że w każdym kroku musimy wykonać dwa wyszukiwania binarne, aby zawęzić kubełek do interesującego nas przedziału.
Pozostaje kwestia znalezienia mediany (czyli k-tego elementu dla k=s/2, gdzie s jest rozmiarem kubełka) w kubełku. Tym razem nie potrzebujemy żadnej struktury danych, ponieważ jest to tylko jedno zapytanie. Działającym liniowo algorytmem wyszukiwania mediany jest algorytm magicznych piątek. Nam wystarczy jego uboższy kuzyn, algorytm Horae’a (którego oczekiwany czas działania jest liniowy, ale pesymistyczny – kwadratowy). Algorytm ten jest bardzo podobny do algorytmu quicksort (również odkrytego przez Hoare’a). Szukamy k-tego elementu w s-elementowym kubełku. Wybieramy losowo element z kubełka, a następnie przesuwamy wszystkie elementy mniejsze na lewo od niego, a większe na prawo (jest to znana z quicksorta operacja partition). Jeżeli wybrany element wypadł na pozycji a, która jest większa od k, to rekurencyjnie szukamy k-tego elementu wśród pierwszych a elementów, w przeciwnym razie szukamy (k-a)-tego elementu wśród ostatnich s-a elementów. Każdy przebieg algorytmu kosztuje nas liniowo od rozmiaru kubełka, jednak oczekujemy, że rozmiary przeszukiwanego obszaru będą malały o połowę przy każdej iteracji. Dlatego średni czas działania algorytmu jest liniowy. Biblioteka STL zawiera implementacje algorytmu Hoare’a pod nazwą nth_element.
Okazuje się, że krok wyszukiwania mediany można wyeliminować. Przypuśćmy, że niezależnie od kubełków dysponujemy również ciągiem indeksów w koleności rosnących wartości (na przykładzie z rysunku byłby to ciąg 0,3,1,5,6,9,4,2,8,7). Mając tę informację znalezienie mediany jest trywialne - indeks mediany będzie bowiem znajdował się na środku owego ciągu. Możemy zatem podobnie jak wcześniej obliczyć zawartość lewego i prawego kubełka na pierwszym poziomie. Zauważmy teraz, że liczby, które trafia do lewego kubełka w ciągu posortowanym będą znajdowały się w pierwszej połowie, natomiast liczby z prawego kubełka - w drugiej połowie. Zatem indeksy znajdujące się w jednym kubełku zawsze tworzą spójny fragment w ciągu posortowanych indeksów. Co więcej, określenie tego fragmentu jest proste - zatem potrafimy znajdować medianę do podziału kubełka w czasie stałym!
Ostatnim usprawnieniem opisywanego algorytmu będzie pozbycie się wyszukiwania binarnego z procedury odpowiadania na zapytanie. Załóżmy, że podczas tworzenia kubełków dla każdego indeksu zapamiętaliśmy jego pozycję w kubełkach. Ponadto, dodając indeks do lewego kubełka zapamiętaliśmy, oprócz owego indeksu, również aktualny rozmiar prawego kubełka (i analogicznie dodając indeks do prawego kubełka). Oczywiście znalezienie przedziału w największym kubełku jest trywialne. Jeżeli teraz pierwszy element przedziału podczas podziału powędrował do lewego kubełka, a my odpowiadając na zapytanie również chcemy zejść do lewego kubełka, to pierwszy element przedziału nie zmienia się (analogicznie dla ostatniego elementu oraz prawego kubełka)! Możemy odczytać jego pozycję w nowym kubełku z obliczonej wcześniej tablicy wszystkich pozycji wszystkich elementów. Jeżeli jednak pierwszy element powędrował do lewego kubełka, a my chcielibyśmy przejść do prawego kubełka, pierwszy element przedziału zmienia się. Zastanówmy się, czy nowy pierwszy element przedziału może być mniejszy (co do wartości indeksu) od starego. Okazuje się, że nie - w przeciwnym wypadku bowiem istniałby w przedziale element mniejszy (co do wartości indeksu) od starego początku, a zatem początek nie byby wcale początkiem. Dlatgo nowym początkiem będzie pierwszy element z prawego kubełka większy (co do wartości indeksu) od starego początku. Zatem nowy początek będzie znajdował się na pozycji, która była rozmiarem prawego kubełka w momencie, kiedy stary początek wędrował do lewego kubełka - tą wartość zaś zapamiętaliśmy! Analogiczne rozumowanie można przeprowadzić dla ostatniego elementu przedziału oraz zamieniając prawy i lewy kubełek miejscami. Umiemy zatem mając przedział w większym kubełku znaleźć w czasie stałym przedział w mniejszym kubełku. W ten sposób zredukowaliśmy czas trwania zapytania do O(log n)
Okazuje się, że lepszej złożoności czasowej nie można uzyskać. Cały algorytm działa w czasie O(n log n + q log n). Załóżmy, że wykonalibyśmy n zapytań - o zerowy, pierwszy, drugi element i tak dalej. W ten sposób posortowalibyśmy nasze etykiety. Koszt takiej operacji wynosiłby O(n log n) (podstawiliśmy q = n). Okazuje się, że jeżeli jedynie porównujemy etykiety między sobą (a nie korzystamy z tego, że są liczbami całkowitymi na przykład), jest to najlepsza możliwa do uzyskania złożoność. Zachęcamy do zmierzenia się z implementacją przedstawionych algorytmów w zadaniach: Query on a tree III, Mediana, Pre-order, któych treści znajdziesz na następnej stronie.
Limit czasowy 1s, limit pamięciowy : 32MB
Dany jest ciąg liczb całkowitych. Twoim zadaniem jest znalezienie w nim -tej liczby w porządku niemalejącym.
Wejście:
W pierwszej linii wejścia dana jest liczba - ilość testów (). Następnie danych jest linii. W każdej linii znajdują się liczby (), a następnie liczb całkowitych (co do modułu nie większych od dwóch miliardów).
Wyjście:
Dla każdego testu należy wypisać -tą liczbę w porządku niemalejącym.
Przykład:
Wejście:
2
6 3 -4 5 66 -2 3 11
8 6 87 23 -13 87 42 100 0 23
Wyjście:
3
87
Limit czasowy 1s, limit pamięciowy : 32MB
Dane jest ukorzenione drzewo z etykietowanymi wierzchołkami. Należy wypisać etykiety wierzchołków w porządku pre-order.
Wejście:
W pierwszej linii wejścia dana jest liczba - ilość wierzchołków drzewa (). W drugiej linii dane jest liczb - są to etykiety wierzchołków. Nastęnie danych jest linii, każda z nich zawiera dwie liczby , (). Oznaczają one, że istnieje krawędź między wierzchołkami oraz . Wszystkie krawędzie na wejściu będą różne. Korzeniem drzewa jest wierzchołek o numerze 1.
Wyjście:
Należy wypisać liczb - etykiety kolejnych wierzchołków w porządku pre-order.
Przykład:
Wejście:
5
23 56 15 83 27
1 3
2 3
4 5
1 5
Wyjście:
23 15 56 27 83
Limit czasowy 5s, limit pamięciowy : 32MB
Dane jest ukorzenione drzewo o etykietowanych wierzchołkach. Należy odpowiadać na zapytania postaci "podaj numer wierzchołka o -tej co do wielkości etykiecie w poddrzewie wierzchołka ".
Wejście:
W pierwszej linii dana jest liczba () - ilość wierzchołków drzewa. Następnie danych jest liczb całkowitych - są to etykiety kolejnych wierzchołków. Następnie danych jest linii, z których każda zawiera dwie liczby , (), które oznaczają, że istnieje krawędź pomiedzy wierzchołkami oraz . Krawędzie nie powtarzają się. Korzeniem drzewa jest wierzchołek o numerze 1. Następnie dana jest liczba () oznaczająca ilość zapytań. Dalej danych jest linii, z których każda zawiera dwie liczby , . Oznaczają one zapytanie o -ty wierzchołek w poddrzewie wierzchołka .
Wyjście:
Dla każdego zapytania należy wypisać szukany numer wierzchołka
Przykład:
Wejście:
5
2 4 65 1 87
4 2
1 3
1 2
2 5
2
3 1
5 1
Wyjście:
3
5