Answer these queries
23.02.2010 - Tomasz Górzny
GSS1Dla porządku i przejrzystości:
Sumy prefiksoweRozwiązywanie zaczniemy od uproszczenia problemu (czyli, jak to zwykle bywa, zanim zmierzymy się z oryginalnym problemem, najpierw próbujemy sił na łatwiejszej wersji), w którym odpowiedzią zapytanie jest po prostu . Jak to wtedy rozwiązać? Z pomocą przychodzą sumy prefiksowe. Idea jest prosta - dla każdego prefiksu ciągu A zapamiętujemy sumę jego elementów, formalnie . W trywialny sposób wyznacza się S w czasie , po czym odpowiadanie na zapytania odbywa się w czasie . Wynika to z zależności oraz . Dla jasności przykład działania: A = 4 -1 -5 8 -3 5 1 S = 0 4 3 -2 6 3 8 9Dla późniejszej wygody A numerujemy od jedynki, a S od zera i uwzględniamy zero na początku. Gdyby , to (oryginalne) zadanie byłoby już rozwiązane, ale oczywiście nie musi tak być (zakładając, że autor testów zachował chociaż minimum przyzwoitości). A więc trzeba dłubać dalej... Odpowiadamy na jedno zapytanie w czasie
Załóżmy teraz, że chcemy odpowiedzieć na tylko jedno zapytanie, oraz mamy
policzone sumy prefiksowe. (Dla ustalenia uwagi ). Powiedzmy, że
nie jesteśmy (jeszcze) zbyt mądrzy i sprawdzamy po kolei możliwe początki
i końce podciągów. Zajmie nam to czas , a algorytm będzie wyglądał
tak:
Drzewo przedziałoweMożemy teraz zauważyć, że dość często pytamy o maksimum z pewnego przedziału (a tak naprawdę, cały algorytm to szereg takich pytań). Może więc nie warto liczyć ich za każdym razem od początku? Moglibyśmy zapamiętać na przykład maksimum z przedziału i już zaoszczędzilibyśmy sobie połowę pracy. Można też zapamiętać więcej i więcej zaoszczędzić... Służy do tego drzewo przedziałowe. Jak sama nazwa wskazuje, jest to drzewo, które przechowuje informacje o pewnych przedziałach. Nasze drzewo będzie binarne, a informacją o przechowywanym przedziale będzie maksymalna z zawartych w nim wartości. Spójrzmy na rysunek:
Korzystając z drzewa możemy już przyspieszyć oryginalny, kwadratowy, algorytm:
Ogólny schemat dla drzewZauważmy, że zamiast max moglibyśmy mieć zupełnie inny parametr, albo zestaw parametrów i nie zmieniłoby to w żaden sposób działania drzew przedziałowych. Z ich punktu widzenia ważne jest, że na podstawie dwóch mniejszych przedziałów można wnioskować o większym będącym ich złączeniem. Taka obserwacja. Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
(4 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com