Answer these queries

23.02.2010 - Tomasz Górzny
TrudnośćTrudnośćTrudnośćTrudność

Sumy sufiksowe

Wprowadzimy teraz sumy sufiksowe. Będą to (prawie) sumy prefiksowe dla odwróconego ciągu. Z dwoma istotnymi różnicami:

  • zamiast sumy zapamiętamy val
  • będziemy rozszerzać ciąg dodając elementy na końcu i przeliczając sumy
Rozszerzenie o A[i] będzie polegać na dodaniu do S wartości A[i] na przedziale [ P[i+1], i ].

Przykład działania:

A  =  4  -2  -2   3  -1  -2   2   2  -6
P  =  0   0   2   0   0   3   0   7   0
S0 =  4
S1 =  2  -2
S2 =  2  -2  -2
S3 =  5   1   1   3
S4 =  4   0   0   2  -1
S5 =  4   0   0   0  -3  -2
S6 =  6   2   2   2  -1   0   2
S7 =  6   2   2   2  -1   0   2   2
S8 =  0  -4  -4  -4  -7  -6  -4  -4  -6
Zauważmy, że to, co będziemy chcieli robić z ciągiem sum sufiksowych to:
  • dodanie liczby do każdego elementu w przedziale (poszerzanie sum o dodatkowy element)
  • pytanie o maksimum z wartości w przedziale (zapytania)
Takich operacji dostarczało nam drzewo z poprzedniego zadania (te z leniwym dodawaniem), więc użyjmy go też teraz! (Stąd obsługa sum sufiksowych będzie nas kosztować $ O(\log N) $.)

Jedno zapytanie

Teraz odpowiemy na jedno prawdziwe zapytanie, czyli niech oba końce będą dowolne. Skorzystajmy z naszych sum sufiksowych. W każdym kroku dodajemy kolejny element ciągu i wyciągamy maksimum z wszystkich sum. Maksimum z tych maksimów jest odpowiedzią na nasze pytanie. To tak jakbyśmy dla każdego końca sprawdzali, czy jest on właściwy.

1
2
3
4
5
6
7
wynik = 0
S = drzewo przedziałowe rozmiaru N zainicjalizowane zerami
for i = 1..N
  // dodaj na przedziale [P[i]+1, i] wartość A[i]
  dodaj(S, P[i]+1, i, A[i])
  // zapytanie o maksimum na przedziale [1, i]
  wynik = max( wynik, zapytanie(S, 1, i) ) 
Osiągamy w ten sposób czas $ O(N \log N) $. Jest to dobry czas, bo $ O(N \log N) $ musimy poświęcić na przetworzenie sum sufiksowych, niezależnie od innych czynników. Jednak $ O(N \log N) $ poświęcamy też na zapytanie. Gdyby było ich Q, to zajęłoby nam to czas $ O(Q N \log N) $. Nie jest to satysfakcjonujące. Często też wykonujemy pracę ewidentnie niepotrzebną - żaden wynik nie poprawi się po dodaniu liczby ujemnej. Nie warto też liczyć, jeżeli kolejna liczba jest dodatnia, bo ona na pewno żadnego wyniku nie pogorszy.

Maksimum na przestrzeni czasu

Zauważmy, że to, co nas interesowało, to maksimum z wartości osiągniętych przez sumy sufiksowe na przestrzeni całego algorytmu. Zapamiętajmy więc kolejny parametr w drzewie przedziałowym - maksimum na przestrzeni czasu. Będzie to najlepsze z maksimów jakie zostało do tej pory osiągnięte dla danego przedziału.

Zobaczmy to na przykładzie:

S - sumy sufiksowe
M - maksima na przestrzeni czasu
A  =  4  -2  -2   3  -1  -2   2   2  -6
P  =  0   0   2   0   0   3   0   7   0
S0 =  4
M0 =  4
S1 =  2  -2
M1 =  4  -2
S2 =  2  -2  -2
M2 =  4  -2  -2
S3 =  5   1   1   3
M3 =  5   1   1   3
S4 =  4   0   0   2  -1
M4 =  5   1   1   3  -1
S5 =  4   0   0   0  -3  -2
M5 =  5   1   1   3  -1  -2
S6 =  6   2   2   2  -1   0   2
M6 =  6   2   2   2  -1   0   2
S7 =  6   2   2   2  -1   0   2   2
M7 =  6   2   2   2  -1   0   2   2
S8 =  0  -4  -4  -4  -7  -6  -4  -4  -6
M8 =  6   2   2   2  -1   0   2   2  -6

Odpowiadamy na wszystkie zapytania

Teraz mocno skorzystamy z tego, że na zapytania wcale nie trzeba odpowiadać w tej samej kolejności, w której zostały zadane. Posortujemy je po końcach. Następnie po kolei dodajemy do sum sufiksowych elementy. Kiedy trafimy na koniec kolejnego zapytania, oznaczmy je (a,b), tzn kiedy dodamy b-ty element ciągu, to pytamy drzewa o maksimum na przestrzeni czasu (M) dla przedziału (a,b) i zapisujemy odpowiedź dla tego zapytania.

1
2
3
4
5
6
7
8
9
10
11
posortuj zapytania niemalejąco po końcach przedziałów
j = 0
S - drzewo przedziałowe rozmiaru N zainicjalizowane zerami
for i = 1 .. N
  // dodaj na przedziale [ P[i]+1, i ] wartość A[i]
  dodaj( S, P[i]+1, i, A[i] ) 
  while zapytania[j].b = i
    // zapytanie o maksimum na przestrzeni czasu
    odp = zapytanie( S, zapytania[j].a, i )
    zapytania[j].odpowiedz = odp
    j = j + 1

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.5
Twoja ocena: Brak Ocena: 4.5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com