3.4 Zbirovi prefksa, razlike susednih elemenata

Zbir svih elemenata niza na pozicijama u intervalu \([a, b]\) se može izračunati kao razlika između zbira svih elemenata na pozicijama u intervalu \([0, b]\) i zbira elemenata na pozicijama u intervalu \([0, a-1]\). Dakle, zbir bilo kog segmenta se može izračunati kao razlika dva zbira prefiksa.

Ova naizgled veoma jednostavna osobina sabiranja može značajno pomoći ubrzanju raznih algoritama u kojima su nam potrebni zbirovi segmenata tj. zbirovi uzastopnih elemenata niza. Naime, ako znamo niz zbirova svih prefiksa niza tj. zbirove na svim intervalima \([0, k)\), za \(k=0\) do \(n\) (a njih možemo izračunati tokom faze pretprocesiranja, inkrementalno, u linearnoj složenosti), tada u konstantnoj složenosti (jednim oduzimanjem) možemo izračunati zbir proizvoljnog segmenta niza.

Da rezimiramo, niz zbirova prefiksa \(Z_k = \sum_{i=0}^{k-1} a_k\) izračunavamo na osnovu veza \(Z_0 = 0, \quad Z_{k+1} = Z_k + a_k, 0 \leq k < n.\)

Tada zbir segmenta \(Z_{ab} = \sum_{i=a}^b a_k,\) računamo efikasno na osnovu veze \(Z_{ab} = Z_{b+1} - Z_a.\)

Implementacija ove tehnike je veoma jednostavna.

vector<int> a(n);
...
// izracunavanje niza prefiksni zbirova
vector<int> ps(n+1);
ps[0] = 0;
for (int i = 0; i < n; i++)
   ps[i+1] = ps[i] + a[i];
   
// izracunavanje zbira segmenta odredjenog pozicijama [a, b]
int zbirSegmenta = ps[b+1] - ps[a];

U jeziku C++ parcijalne zbirove je moguće izračunati i korišćenjem bibliotečke funkcije partial_sum, koja, naravno, radi u linearnoj složenosti. Funkciji se prosleđuju dva iteratora na deo niza koji se sabira, kao i iterator na početak niza u koji se smeštaju rezultati (pošto se unapred zna koliko će elemenata biti, taj niz se unapred alocira).

// izracunavanje niza prefiksni zbirova
vector<int> ps(n+1);
partial_sum(begin(a), end(a), begin(ps));

Ipak, direktno inkrementalno izračunavanje niza zbirova prefiksa je toliko jednostavno da se ova funkcija ne koristi često.

Niz zbirova prefiksa datog niza možemo izračunati u linearnoj složenosti, ali važi i obratno. Od niza zbirova prefiksa, u linearnoj složenosti možemo izračunati elemente originalnog niza. Važi čak i jače tvrđenje od toga, jer svaki konkretni element niza možemo naći u konstantnoj složenosti, oduzimanjem dva susedna zbira prefiksa (za svako \(0 \leq k < n\), važi \(a_k = Z_{k+1} - Z_{k}\)). Zato prelazak sa niza na zbirove njegovih prefiksa možemo smatrati promenom reprezentacije podataka čuvanjem istih podataka u efikasnijoj strukturi podataka (često nema smisla čuvati i jedno i drugo istovremeno u memoriji).

Primetimo ogromnu sličnost sa integralnim i diferencijalnim računom. Izračunavanje zbirova prefiksa odgovara određenom integraljenju, razlika zbirova prefiksa odgovara Njutn-Lajbnicovoj formuli, dok izračunavanje razlike susednih elemenata odgovara diferenciranju. Integraljenje i diferenciranje su međusobno inverzne operacije.

Dualan pristup zbirovima prefiksa je promena reprezentacije u kojoj umesto niza čuvamo niz razlika susednih elemenata.

\[R_0 = a_0, \quad R_k = a_{k} - a_{k-1}, 1 \leq k \leq n.\]

Povratak na orginalni niz se onda može izvršiti u linearnoj složenosti tako što izračunamo zbirove prefiksa niza razlika. Ova reprezentacija nam omogućava da veoma efikasno menjamo segmente niza tako što sve elemente iz nekog zadatog segmenta uvećamo ili umanjimo za neku fiksnu vrednost, što može biti veoma korisna operacija u nekim primenama (koje ćemo ilustrovati kroz zadatke).

Na ideji niza prefiksnih zbirova možemo izgraditi i strukturu podataka koja nam omogućava da se brzo izračuna koliko proizvoljni segment niza ima elemenata koji zadovoljavaju neki dati uslov. Dovoljno je izračunati niz zbirova prefiksa niza koji ima jedinice na mestima na kojima se u originalnom nizu nalazi element koji zadovoljava taj uslov i nule na ostalim mestima.

Slično nizu zbirova prefiksa, možemo čuvati i niz vrednosti neke druge statistike. Ako se statistika izračunava operacijom koja ima inverznu operaciju (kao što je oduzimanje inverzna operacija operaciji sabiranja), onda je možemo koristiti na potpuno isti način kao niz zbirova prefiksa. Na primer, ako znamo da su svi elementi niza različiti od nule, tada možemo čuvati niz proizvoda prefiksa. Proizvod bilo kog segmenta možemo ostvariti deljenjem proizvoda dva prefiksa (kao što se zbir segmenta određuje oduzimanjem dva zbira prefiksa). Međutim, ako niz sadrži nulu, stvari se komplikuju jer će proizvod svakog prefiksa nakon te nule biti jednak nuli, pa ne možemo izvršiti deljenje. U tom slučaju je pored niza proizvoda prefiksa potrebno čuvati i niz u kome čuvamo broj nula do tekuće pozicije u originalnom nizu.

Ako operacija nema inverznu (poput operacija minimuma, maksimuma, NZD, NZS), tada njeno efikasno računanje za proizvoljni segment niza zahteva kompleksnije strukture podataka (na primer, segmentno drvo koje će detaljno biti opisano u narednim kursevima). Ponekad se traži računanje statistike niza koji se dobija izbacivanjem jednog ili više uzastopnih elemenata niza (tj. izbacivanjem nekog segmenta). Tu nam može pomoći istovremeno poznavanje niza statistika prefiksa i niza statistika sufiksa. Nizovi statistika prefiksa i sufiksa se mogu izračunati u vremenu \(O(n)\), da bi se nakon toga statistike niza bez izbačenih pojedinačnih segmenata mogle računati u vremenu \(O(1)\).

Zadatak: Maksimalni zbir segmenta

Ovaj zadatak je ponovljen u cilju ilustrovanja različitih tehnika rešavanja.

Tekst zadatka.

Rešenje

Zbirovi prefiksa

Analiziraćemo svaku poziciju u nizu i razmatraćemo sve segmente koji se na toj poziciji završavaju. Zbir elemenata svakog od njih se može izračunati kao razlika između zbira prefiksa do te tekuće pozicije i odgovrajućeg prefiksa pre te pozicije. Da bi razlika bila što veća, umanjilac mora biti što manji. Dakle, od svih segmenata koji se završavaju na tekućoj poziciji, najveći zbir se dobija oduzimanjem minimalnog zbira prefiksa pre tekuće pozicije od zbira prefiksa do tekuće pozicije. Minimalni zbir prefiksa niza ne moramo da određujemo svaki put iz početka, već i njega možemo inkrementalno da ažuriramo. Analiziramo jednu po jednu poziciju, za svaku određujemo najveći zbir segmenta koji se završava na toj poziciji i ako je ona veća od globalnog maksimuma, ažuriramo maksimum. Pošto se maksimalni segment sigurno završava na nekoj poziciji i najveći je od svih takvih, a pošto eksplicitno proveravamo sve pozicije, sigurni smo da će predloženi algoritam zaista pronaći maksimalni segment.

Složenost ovog rešenja je \(O(n)\), pa je ovo rešenje optimalne složenosti.

int zbir_prefiksa = 0;
int min_zbir_prefiksa = zbir_prefiksa;
int max_zbir_segmenta = 0;
for (int i = 0; i < n; i++) {
  int x;
  cin >> x;
  zbir_prefiksa += x;
  int zbir = zbir_prefiksa - min_zbir_prefiksa;
  if (zbir > max_zbir_segmenta)
    max_zbir_segmenta = zbir;
  if (zbir_prefiksa < min_zbir_prefiksa)
    min_zbir_prefiksa = zbir_prefiksa;
}
cout << max_zbir_segmenta << endl;

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  
  int zbir_prefiksa = 0;
  int min_zbir_prefiksa = zbir_prefiksa;
  int max_zbir_segmenta = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    zbir_prefiksa += x;
    int zbir = zbir_prefiksa - min_zbir_prefiksa;
    if (zbir > max_zbir_segmenta)
      max_zbir_segmenta = zbir;
    if (zbir_prefiksa < min_zbir_prefiksa)
      min_zbir_prefiksa = zbir_prefiksa;
  }
  cout << max_zbir_segmenta << endl;
  
  return 0;
}