Answer these queries

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

GSS1

Dla porządku i przejrzystości:
  • $  A[1] \ldots A[n]  $ - ciąg wejściowy
  • $  val(A[i] \ldots A[j]) = A[i]+A[i+1]+ \ldots +A[j]  $

Sumy prefiksowe

Rozwią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 $ (a,b) $ jest po prostu $ val(A[a] \ldots A[b]) $. 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 $ S[i] = A[1] + \ldots + A[i] $. W trywialny sposób wyznacza się S w czasie $ O(n) $, po czym odpowiadanie na zapytania odbywa się w czasie $ O(1) $. Wynika to z zależności $ S[i] = S[i-1] + A[i] $ oraz $ A[i]+\ldots +A[j] = S[j]-S[i-1] $.

Dla jasności przykład działania:

A =    4 -1 -5  8 -3  5  1
S = 0  4  3 -2  6  3  8  9
Dla późniejszej wygody A numerujemy od jedynki, a S od zera i uwzględniamy zero na początku.

Gdyby $ Ai \ge 0 $, 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 $ O(N^2) $

Załóżmy teraz, że chcemy odpowiedzieć na tylko jedno zapytanie, oraz mamy policzone sumy prefiksowe. (Dla ustalenia uwagi $ a = 1, b = N $). 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 $ O(n^2) $, a algorytm będzie wyglądał tak:

1
2
3
4
wynik = 0
for i = 0 .. N
  for j = i+1 .. N
    wynik = max(wynik, S[j]-S[i])
Możemy zauważyć, że zawsze dla ustalonego początku wybieramy koniec, któremu odpowiada możliwie największa suma prefiksowa. I odwrotnie - dla każdego końca najlepszy jest możliwie najmniejszy prefiks. Uzbrojeni w te informacje możemy napisać algorytm wyznaczający odpowiedź w czasie $ O(n) $, ale na razie zrobimy to tak:
1
2
3
4
5
6
wynik = 0
for i = 0 .. N
  maxSj = S[i]
  for j = i+1 .. N
    maxSj = max(masSj, S[j])
  wynik = max(wynik, maxSj-S[i])

Drzewo przedziałowe

Moż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 $ [N/2 \ldots N ] $ 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:

Prostokąty reprezentują węzły drzewa. Mają w sobie zapisane informacje o tym, za jaki przedział odpowiadają i jakie jest na nim maksimum. Takie drzewo można zbudować na przykład tak:
1
2
3
4
5
6
7
8
9
10
11
zbuduj(a,b) // buduje drzewo dla przedziału [a,b]
  v.a = a
  v.b = b
  if a = b
    v.max = S[a]
  else
    v.c = (a+b)/2
    v.prawy = zbuduj(a,c)
    v.lewy = zbuduj(c+1,b)
    v.max = max(prawy.max, lewy.max)
  return v
Składnikami wierzchołka są:
  • a, b, c - początek, koniec i środek przedziału (zazwyczaj nie będziemy ich pamiętać bezpośrednio)
  • lewy i prawy - poddrzewa odpowiedzialne za odcinki [a,c] i [c+1, b]
  • max - maksimum na przedziale [a,b]
Po chwili refleksji można dojść do wniosku, że znalezienie maksimum na dowolnym przedziale wymaga popatrzenia na co najwyżej $ 2\log(n) $ wierzchołków.

Korzystając z drzewa możemy już przyspieszyć oryginalny, kwadratowy, algorytm:

1
2
3
4
5
D = zbuduj(0, N)
wynik = 0
for i = 0..N
  maxSj = max z drzewa na przedziale j..N
  wynik = max(wynik, maxSj-S[i])

Ogólny schemat dla drzew

Zauważ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.5
Twoja ocena: Brak Ocena: 4.5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com