Za razliku od prethodnih, statičkih upita nad rasponima, ovde ćemo razmatrati tzv. dinamičke upite nad rasponima koji dozvoljavaju da se niz menja tokom vremena, tako da je potrebno razviti naprednije strukture podataka koje omogućavaju izvršavanje oba tipa upita (čitanje i ažuriranje) efikasno.
Naime, niz zbirova prefiksa omogućava efikasno izračunavanje zbirova segmenata niza kod nizova čiji se sadržaj ne menja. Sa druge strane, niz zbirova prefiksa ne omogućava efikasno ažuriranje elemenata niza, jer je pri svakoj izmeni nekog elementa niza potrebno ažurirati i zbirove prefiksa, što je naročito neefikasno kada se ažuriraju elementi blizu početka niza (složenost najgoreg slučaja je \(O(n)\)), pa se ne mogu primenjivati u situacijama u kojima su upiti izračunavanja zbirova segmenata isprepleteni sa upitima ažuriranja vrednosti elemenata niza.
Slično, niz razlika susednih elemenata dopušta stalna ažuriranja elemenata niza. Međutim, izvršavanje upita kojima se zahteva određivanje elemenata niza podrazumeva rekonstrukciju sadržaja niza na osnovu niza razlika, što je složenosti \(O(n)\). Stoga niz razlika nije poželjno upotrebljavati u situacijama kada su upiti uvećavanja segmenata i očitavanja vrednosti elemenata niza isprepletani.
Problemi koje ćemo razmatrati u ovom odeljku su specifični po tome što omogućavaju da se upiti ažuriranja niza i očitavanja njegovih statistika javljaju isprepletano. Za početak razmotrimo malo jednostavniji problem.
Problem. Definisati strukturu podataka koja obezbeđuje efikasno izračunavanje zbirova segmenata datog niza određenih pozicijama \([a, b]\) (samim tim i pojedinačnih elemenata niza), kao i efikasno menjanje vrednosti pojedinačnih elemenata niza.
Videćemo da neke strukture podataka dopuštaju da se umesto zbira koriste i neke druge operacije. U narednim poglavljima ćemo razmotriti i složeniji problem u kom će biti dopušteno ažuriranje segmenata niza (a ne samo pojedinačnih elemenata).
Dakle, za početak pretpostavljamo da imamo dat niz od \(m\) operacija od kojih je svaka ili izračunavanje zbira nekog segmenta ili ažuriranje pojedinačnog elementa niza i cilj je minimizovati ukupno vreme izvršavanja ovog niza operacija. U ovom slučaju nam nije od koristi struktura podataka kod koje se jedna od ove dve operacije izvršava efikasno, a druga neefikasno jer se može desiti da je većina (ili su sve) od \(m\) datih operacija baš tog drugog tipa. Naravno, treba uzeti u obzir i vreme inicijalizacije strukture podataka, međutim, pošto se inicijalizacija vrši samo jednom, za razliku od upita za koje pretpostavljamo da se izvršavaju puno puta, fokusiraćemo se na složenost vremena izvršavanja upita.
U nastavku ćemo razmotriti dve različite, ali donekle slične strukture podataka koje daju efikasno rešenje prethodnog i njemu sličnih problema: segmentno drvo i Fenvikovo drvo. Ideja obe ove strukture podataka na neki način nalikuje korišćenju prefiksnih suma: čuvaju se zbirovi nekih unapred pogodno izabranih segmenata i oni se koriste za efikasno računanje zbira proizvoljnog segmenta.
Poglavlja: