ALGORYTMICZNA PRZYGODA
Kaliny

Archiwum

Polecam

Platformy do rozwiązywania zadań:
Strony do nauki:

Sumy prefiksowe

Cześć! W tym poście chciałabym pokazać Wam niezwykle przydatny algorytm - sumy prefiksowe.

Mamy ciąg n liczb i chcielibyśmy odpowiedzieć na q zapytań, w których mamy podane dwie liczby: a oraz b.
Musimy powiedzieć, ile wynosi suma liczb w tym ciągu od elementu a-tego do elementu b-tego (włącznie).

Przykład:

Input
5 //n
1 8 3 5 2 //ciąg liczb
3 //q
1 2 // a oraz b
3 5 // a oraz b
1 1 // a oraz b

Output
9
10
1


Rozwiązanie 1 (brutalne)
Za każdym razem, gdy otrzymujemy zapytanie, obliczamy sumę liczb od na indeksach od 1 do n (przy założeniu,
że indeksujemy od 1). Złożoność tego rozwiązania to O(n*q).

Rozwiązanie 2 (drzewa przedziałowe)
Jest to dosyć trudny algorytm i postaram się go opisać w innym poście.
Jego złożoność to O(q*log2(n)).

Rozwiązanie 3 (sumy prefiksowe)
Ten algorytm jest niezwykle szybki - działa w złożoności O(n+q).
Aby z niego skorzystać, musimy najpierw obliczyć sumę na każdym przedziale od 1 do i:

1 2 3 4 5 //i
1 8 3 5 2 //ciąg liczb
1 9 12 17 19 //pref[i]

Każda kolejna wartość pref to pref[i-1]+liczby[i], czyli:
pref[i] = pref[i-1]+liczby[i], przy czym pref[1] jest równe liczby[1] (jeśli indeksujemy od 1).

Umiemy już odczytać sumę od 1 do x.
Ale jak odczytać sumę od a do b, jeśli a jest różne od 1?

Przyjrzyjmy się dokładnie sumom, które obliczyliśmy.

1 8 3 5 2 //ciąg liczb
1 9 12 17 19 //pref[i]

Zauważmy, że suma od elementu 3 do 5 to
suma od elementu 1 do 5 - suma od elementu 1 do 2

Czyli
suma od elementu 3 do 5 = 19 - 9 = 10
Zgadza się?
3 + 5 + 2 = 10

Tak więc możemy odpowiadać na zapytania w czasie stałym, ponieważ:
suma od a do b = pref[b]-pref[a-1]
Trzeba uważać na przypadek, w którym a = 1. W tym przypadku, jeśli indeksujemy od zera, mimo wszystko warto
zacząć liczyć sumy prefiksowe od 1, a pref[0] ustawić na 0.

Podsumowując, finalna złożoność tego rozwiązania to O(q+n).



Mam nadzieję, że wszystko jest zrozumiałe, a w razie problemów śmiało piszcie w zakładce Kontakt :)


Do zobaczenia w kolejnym poście!

O blogu

Zapraszam na moją algorytmiczną przygodę!

  • przygotowuję się do Olimpiady Informatycznej Juniorów oraz do Konkursu Logia;
  • biorę udział w Olimpijskim Kole Informatycznym;
  • pokonuję algorytmiczne trudności;
  • piszę programy w C++ i w Pythonie;
  • dzielę się swoimi przemyśleniami oraz pomysłami.
  • Ostatnie posty