Za početak ćemo razmatrati statičke upite raspona, kod kojih je zadatak omogućiti efikasno izvršavanje potencijalno velikog broja različitih upita nad segmentima datog niza, pri čemu se vrednosti u nizu ne menjaju.
Problem. Definisati strukturu podataka koja obezbeđuje efikasno izračunavanje zbirova segmenata datog niza (segment određen pozicijama \([a, b]\) se sastoji od uzastopnih elemenata niza od pozicije \(a\) do pozicije \(b\), uključujući i njih).
Rešenje grubom silom bi smestilo sve elemente u niz \(x\) i pri svakom upitu iznova računalo zbir elemenata na pozicijama iz intervala \([a, b]\) koji odgovara tom upitu. Ukupno vreme da se svi upiti izvrše je reda \(O(mn)\), gde je sa \(m\) označen broj upita, a sa \(n\) dužina niza, što je u slučaju dugačkih nizova i velikog broja upita nedopustivo neefikasno. I složenost najgoreg slučaja i amortizovana složenost izvršavanja jednog upita su reda \(O(n)\).
Jednostavno rešenje je zasnovano na ideji da umesto da čuvamo elemente niza \(x\), čuvamo niz zbirova prefiksa (engl. prefix sum array) niza \(P_0 = 0\), \(P_{i+1}=\sum_{k=0}^i x_k\) za \(0\leq i\leq n\). Dakle, zbir \(P_i\) čuva zbir prvih \(i\) elemenata niza (pošto brojanje pozicija počinje od nule, zbir elemenata \(x_0, \ldots, x_i\) sadrži \(i+1\) sabirak i jednak je \(P_{i+1}\)). Zbir elemenata svakog segmenta \([a, b]\) onda možemo razložiti na razliku prefiksa niza \(x\) do elementa \(b\) i prefiksa do elementa \(a-1\):
\[\sum_{k=a}^{b}x_k=\sum_{k=0}^{b}x_k-\sum_{k=0}^{a-1}x_k=P_{b+1}-P_a.\]
Svi zbirovi prefiksa \(P_i\) niza \(x\) mogu se izračunati algoritmom složenosti \(O(n)\) i smestiti u dodatni (a ako je ušteda memorije bitna, onda čak i u originalni) niz. Nakon ovakvog pretprocesiranja, zbir svakog segmenta se može izračunati algoritmom složenosti \(O(1)\), pa je ukupna složenost izvršavanja \(m\) upita računanja zbira elemenata nekog segmenta niza \(x\) jednaka \(O(n + m)\).
Ako je poznat niz zbirova prefiksa \(P\), tada se polazni niz \(x\) može rekonstruisati računanjem niza razlika susednih elemenata niza prefiksa: \(x_i=P_{i+1}-P_i\) za \(0\leq i < n\).
U dvodimenzionalnom slučaju dovoljno je za svaki element matrice na poziciji \((v, k)\) pamtiti zbir \(P_{v+1,k+1}\) elemenata pravougaonog segmenta kojem je gornje levo teme polje \((0, 0)\), a donje levo \((v, k)\), pri čemu se u vrsti i koloni 0 nalaze nule. Tada se zbir proizvoljnog segmenta određenog gornjim-levim temenom \((v_1, k_1)\) i donjim-desnim temenom \((v_2, k_2)\) može izraziti kao \(P_{v_2+1, k_2+1} - P_{v_2+1, k_1} - P_{v_1, k_2+1} + P_{v_1, k_1}\), kao što je ilustrovano na slici 1.
Niz zbirova prefiksa ima različite primene. Na primer, u obradi slika koristi se za izračunavanje različitih proračuna nad regionima slike (poput zbirova) koji omogućavaju razne operacije nad slikom poput detekcije ivica, zamućenja i drugih. Zbirovi prefiksa imaju primenu i u analizi podataka, obradi podataka, finansijskoj analizi i dr.
Donekle srodan problem je i sledeći.
Problem. Definisati strukturu podataka koja omogućava efikasno izvršavanje upita oblika \(([a, b], c)\), koji podrazumevaju da se svi elementi niza \(x\) na pozicijama iz segmenta \([a, b]\) uvećaju za vrednost \(c\). Potrebno je odrediti sadržaj niza \(x\) nakon izvršavanja svih upita.
Direktno rešenje bi za svaki upit u petlji uvećavalo sve elemente niza \(x\) na pozicijama iz segmenta \([a, b]\). Složenost tog naivnog pristupa je \(O(mn)\), gde je sa \(m\) označen broj upita, a sa \(n\) dužina niza.
Mnogo efikasnije rešenje se može dobiti ako se umesto elemenata niza pamti niz razlika svaka dva susedna elementa niza (engl. difference array): \(R_0=x_0, R_i=x_i-x_{i-1}\) za svako \(i\) između \(1\) i \(n-1\). Ključni uvid je da se tokom uvećavanja svih elemenata segmenta \([a,b]\) niza \(x\) za vrednost \(c\) menjaju samo razlike između elemenata na pozicijama \(a\) i \(a-1\) (razlika \(R_a\) se uvećava za \(c\)) kao i između elemenata na pozicijama \(b+1\) i \(b\) (razlika \(R_{b+1}\) se umanjuje za \(c\)). Ako znamo sve elemente niza, tada niz razlika susednih elemenata možemo veoma jednostavno izračunati algoritmom složenosti \(O(n)\). Sa druge strane, ako znamo niz razlika nekog niza, tada taj niz možemo takođe veoma jednostavno rekonstruisati, izračunavajući zbirove prefiksa niza razlika, čija je vremenska složenost \(O(n)\). Na taj način, na osnovu razlika elemenata finalnog niza, možemo lako rekonstruisati taj finalni niz.
U narednom apletu možete proveriti svoje razumevanje i videti kako se ponaša niz razlika susednih elemenata.
Ako ne želimo da u implementaciji prvi i poslednji element niza tretiramo drugačije od ostalih, možemo pretpostaviti da početni niz i niz razlika proširujemo sa po jednom nulom sa leve i desne strane (tada je \(R_i = x_{i+1} - x_i\), za svako \(i\) od \(0\) do \(n-1\)).
Može se primetiti da se rekonstrukcija originalnog niza vrši zapravo izračunavanjem prefiksnih zbirova niza razlika susednih elemenata, što ukazuje na duboku vezu između ove dve tehnike. Zapravo, razlike susednih elemenata predstavljaju određeni diskretni analogon izvoda funkcije, dok prefiksni zbirovi onda predstavljaju analogon određenog integrala. Izračunavanje zbira segmenta kao razlike dva zbira prefiksa odgovara Njutn-Lajbnicovoj formuli.