1.4.3 Ažuriranje segmenata

I segmentna i Fenvikova drveta podržavaju efikasno izračunavanje zbirova određenih segmenata niza (engl. range-query), pa samim tim i određivanje pojedinačnih vrednosti niza (engl. point-query), kao i ažuriranje¹ pojedinačnih elemenata niza (engl. point-update), dok ažuriranje celih segmenata niza odjednom (engl. range-update) nije direktno podržano. Naime, ako se ono svede na pojedinačno ažuriranje svih elemenata unutar segmenta, dobija se loša složenost (u najgorem slučaju vrši se \(n\) ažuriranja koja imaju pojedinačnu složenost \(O(\log{n})\), pa je ukupna složenost \(O(n\log{n})\)). Sa druge strane, čuvanje niza razlika omogućava efikasno ažuriranje celih segmenata (engl. range-update), pa samim tim i pojedinačnih elemenata (engl. point-update), ali ne i efikasno određivanje pojedinačnih elemenata niza (engl. point-query) niti zbirova segmenata (engl. range-query).

U nastavku ćemo videti nekoliko načina da se naprave strukture koje efikasno podržavaju sve navedene operacije.

Drvo nad nizom razlika

Primetimo da se ne zahteva mogućnost efikasnog određivanja statistika segmenata (range query).

Osnovna ideja rešenja je da se održava niz razlika susednih elemenata polaznog niza i da se taj niz razlika čuva u Fenvikovom drvetu (ili, analogno, u segmentnom drvetu).

• Uvećavanje svih elemenata segmenata polaznog niza za neku vrednost \(v\), svodi se na promenu dva elementa niza razlika, što se uz održavanje drveta može uraditi u vremenu \(O(\log{n})\).
• Rekonstrukcija elementa polaznog niza na osnovu niza razlika svodi na izračunavanje zbira odgovarajućeg prefiksa, što se pomoću Fenvikovog drveta može uraditi veoma efikasno, u vremenu \(O(\log{n})\).

Na ovaj način, i ažuriranje celih segmenata niza odjednom i očitavanje pojedinačnih elemenata možemo postići algoritmima složenosti \(O(\log{n})\), što nije bilo moguće samo uz korišćenje niza razlika (uvećavanja svih elemenata nekog segmenta je tada bilo složenosti \(O(1)\), ali je očitavanje vrednosti iz niza bilo složenosti \(O(n)\)). Dakle, ako Fenvikovo ili segmentno drvo izgradimo nad nizom razlika umesto nad originalnim nizom, gubimo mogućnost efikasnog izračunavanja statistika segmenata (range query), ali dobijamo mogućnost ažuriranja segmenata (range update).

Dva drveta razlika

Na kraju, opisaćemo nekoliko struktura podataka koje omogućavaju efikasno izvršavanje sve četiri vrste upita.

Efikasno uvećanje svih elemenata u datom segmentu za istu vrednost i izračunavanje zbirova segmenata moguće je implementirati održavanjem dva Fenvikova ili segmentna drveta.

Prvo od njih će čuvati razlike originalnog niza i omogući će nam da efikasno uvećavamo segmente i izračunavamo pojedinačne elemente originalnog niza.

Ako je originalni niz dužine inicijalizovan nulama, nakon uvećanja svih elemenata sa pozicija iz segmenta \([a, b]\) za vrednost \(v\) dobijamo niz:

koji se može predstaviti nizom razlika:

Sabiranjem prefiksa niza razlika možemo dobiti bilo koji pojedinačni element početnog niza (ako je niz razlika u Fenvikovom ili segmentnom drvetu, složenosti ovog postupka je \(O(\log{n})\)).

Cilj nam je da izračunamo prefiksne zbirove originalnog niza (njega ne možemo čuvati u Fenvikovom ili segmentnom drvetu, zato što nam je potrebno ažuriranje njegovih segmenata, a ne pojedinačnih elemenata).

Prefiksni zbirovi originalnog niza su:

• Prefiksni zbirovi \(P_k\) na pozicjama \(k\) levo od pozicije \(a\) (tj. \(k < a\)) jednaki su nuli (jer su vrednosti \(A_k\) originalnog niza levo od te pozicije jednaki nuli).
• Prefiksni zbirovi \(P_k\) na pozicijama \(k\) između \(a\) i \(b\) (tj. \(a \leq k \leq b\)) jednaki su \((k-a+1)\cdot v\), gde je \(v=A_k\) vrednost koja se nalazi na poziciji \(k\) u originalnom nizu.
• Prefiksni zbirovi \(P_k\) na pozicijama \(k\) desno od pozicije \(b\) (tj. \(k > b\)) jednaki su \((b-a+1)\cdot v\).

Dakle, važi:

\[P_k = \sum_{i=1}^k A_i=\left\{ \begin{array}{ll} 0 & k < a \\ (k-(a-1))\cdot v & a\le k\le b \\ (b-a+1)\cdot v & k>b \end{array} \right. \]

Ključna ideja je da uporedimo ove tražene zbirove sa vrednostima niza koji na svakoj poziciji \(k\) sadrži vrednost \(k\cdot A_k\), tj. da razmotrimo razlike \(X_k = kA_k - P_k\).

• U prvom slučaju (kada je \(k < a\)) je \(A_k=P_k=0\), pa je i \(X_k=0\).
• U drugom slučaju (kada je \(a \leq k \leq b\)) je \(P_k = (k-a+1)\cdot A_k\), pa je \(X_k = kA_k - (k-a+1)A_k = (a-1)A_k\).
• U trećem slučaju (kada je \(k > b\)) je \(P_k = (b-a+1)\cdot v\), dok je \(A_k=0\), pa je \(X_k = -(b-a+1)\cdot v\).

Drugim rečima, svaki zbir prefiksa \(P_k\) smo razložili na razliku \(kA_k - X_k\):

\[P_k = \sum_{i=1}^k A_i=k \cdot A_k - X_k =\left\{ \begin{array}{ll} k\cdot 0 - 0 & k < a \\ k\cdot v - (a-1)\cdot v & a\le k \le b \\ k\cdot 0 - (-(b - a + 1))\cdot v & k>b \end{array} \right. \]

Niz \(X_k\), dakle, nakon ažuriranja originalnog niza ima sledeće vrednosti:

Ako bismo u svakom trenutku poznavali vrednosti u nizu \(X_k\), tada bismo vrednosti \(P_k\) lako mogli izračunati pomoću formule \(P_k = kA_k - X_k\). Vrednosti \(A_k\) lako izračunavamo pomoću Fenvikovog ili segmentnog drveta u kome čuvamo razlike tog niza. Međutim, i niz \(X_k\) je takav da mu se pri svakom ažuriranju povezani segmenti uvećavaju tj. umanjuju za istu vrednost, tako da se i on može lako rekonstruisati ako bi se njegove razlike čuvale u drugom Fenvikovom ili segmentnom drvetu. Naime, niz razlika ovog niza se menja ovako:

Dakle, održavamo dva drveta: \(D_A\) u kome čuvamo razlike niza \(A\) i \(D_X\) u kome čuvamo razlike niza \(X\). Prvo inicijalizujemo razlikama niza \(A\), a drugo nulama.

Operacija uvećanja svih elemenata sa pozicija iz \([a, b]\) za vrednost \(v\) se svodi na sledeće operacije nad drvetima:

• \(\mathit{uvecaj}(D_A, a, v)\)
• ako je \(b < n\) onda \(\mathit{uvecaj}(D_A, b+1, -v)\)
• \(\mathit{uvecaj}(D_X, a, (a-1)v)\)
• ako je \(b < n\) onda \(\mathit{uvecaj}(D_X, b+1, -bv)\)

Operacija izračunavanje vrednosti niza \(A\) na poziciji \(k\) tj. vrednosti \(A_k\) se svodi na izračunavanje prefiksne sume prvih \(k\) elemenata Fenvikovog drveta \(D_A\).

• \(A_k = \mathit{zbir\_prefiksa}(D_A, k)\)

Operacija izračunavanja zbira prefiksa elemenata niza \(A\) dužine \(k\) se svodi na izračunavanje vrednosti

• \(P_k = kA_k - X_k = k\cdot\mathit{zbir\_prefiksa(D_A, k)} - \mathit{zbir\_prefiksa}(D_X, k)\)

Operacija izračunavanja zira segmenta sa pozicija \([a, b]\) niza \(A\) se svodi na izračunavanje vrednosti:

• \(S_{ab} = P_b - P_{a-1}\)

Pri tom je \(P_0 = 0\).

Dakle, na ovaj način možemo postići dobru složenost za sva 4 tipa operacija.

Lenjo ažuriranje segmentnog drveta

Opišimo sada još jedno rešenje prethodnog problema, tj. još jednu strukturu podataka koja omogućava efikasno izvršavanje sve četiri vrste upita. Za razliku od prethodne, ova struktura omogućava i izračunavanje nekih drugih statistika (ne samo zbira elemenata).

Podsetimo se, segmentna drveta omogućavaju efikasno ažuriranje pojedinačnih elemenata i izračunavanje zbirova segmenata (samim tim i određivanje vrednosti pojedinačnih elemenata), međutim, ne omogućavaju efikasno ažuriranje svih elemenata datog segmenta \([a, b]\) (tj. njihovo uvećanje za datu vrednost ili njihovu zamenu datom vrednošću). Ovo se može postići u vremenu \(O(\log n)\) ako se na segmentno drvo primeni tehnika lenje propagacije (engl. lazy propagation). Ona je primer strategije lenjog izvršavanja kojim se izračunavanja odlažu sve dok odgovarajuće vrednosti nisu neophodne. Tehnika lenje propagacije se dosta oslanja na rad sa segmentnim drvetom odozgo naniže. Jednostavnosti radi, tehniku ćemo predstaviti kroz primer upita uvećavanja segmenata za datu vrednost.

Svaki čvor u segmentnom drvetu čuva zbir nekog segmenta orignalnog niza. Ako se taj segment u celosti sadrži unutar segmenta koji se ažurira, možemo unapred izračunati za koliko se povećava vrednost u tom čvoru. Naime, ako se svaka vrednost u segmentu povećava za \(v\), tada se vrednost zbira tog segmenta povećava za \(k \cdot v\), gde je \(k\) broj elemenata u tom segmentu. Vrednost zbira u tom čvoru time biva ažurirana u konstantnom vremenu, ali vrednosti zbirova unutar poddrveta kojima je taj čvor koren (uključujući i vrednosti u listovima koje odgovaraju vrednostima polaznog niza) i dalje ostaju neažurne. Njihovo ažuriranje zahtevalo bi linearno vreme, što je nedopustivo skupo. Ključna ideja je da se ažuriranje tih vrednosti odloži i da se one ne ažuriraju odmah, već samo kada zatrebaju tokom nekog naknadnog upita, tj. tokom neke kasnije posete tim čvorovima (koja se inače vrši u sklopu tog kasnijeg upita, a ne posebno u cilju ažuriranja vrednosti). Naime, ne želimo da te čvorove posećujemo samo zbog ovog ažuriranja, već ćemo ažuriranje uraditi usput, tokom neke druge posete tim čvorovima koja bi se svakako morala desiti.

Postavlja se pitanje kako da signaliziramo da vrednosti zbirova u nekom poddrvetu nisu ažurne i dodatno ostavimo uputstvo na koji način ih treba ažurirati. U tom cilju u svakom od čvorova pored vrednosti zbira segmenta čuvamo i dodatni koeficijent lenje propagacije. Ako drvo u svom korenu ima koeficijent lenje propagacije \(c\) koji je različit od nule, to znači da vrednosti zbirova u celom tom drvetu nisu ažurne i da je svaki od listova tog drveta potrebno povećati za \(c\) i u odnosu na to ažurirati i vrednosti zbirova u svim unutrašnjim čvorovima tog drveta (uključujući i koren). Ažuriranje se može odlagati sve dok vrednost zbira u nekom čvoru ne postane zaista neophodna, a to je tek prilikom upita izračunavanja vrednosti zbira nekog segmenta. Ipak, vrednosti zbirova u čvorovima ćemo ažurirati i češće i to zapravo prilikom svake posete čvoru – bilo u sklopu operacije uvećanja vrednosti iz nekog segmenta pozicija polaznog niza, bilo u sklopu upita izračunavanja zbira nekog segmenta. Naime, na početku obe rekurzivne funkcije možemo proveriti da li je vrednost koeficijenta lenje propagacije tekućeg čvora različita od nule i ako jeste, ažurirati vrednost zbira u tom čvoru tako što ćemo ga uvećati za proizvod tog koeficijenta i broja elemenata koji taj čvor pokriva, zatim koeficijente lenje propagacije oba njegova deteta uvećati za taj koeficijent, a koeficijent lenje propagacije tog čvora postaviti na nulu (time koren drveta koji trenutno posećujemo postaje ažuran, a njegovim poddrvetima se daje uputstvo kako ih u budućnosti ažurirati). Primetimo da se na ovaj način izbegava ažuriranje celog drveta odjednom, već se ažurira samo koren, što je operacija složenosti \(O(1)\).

Imajući ovo u vidu, razmotrimo kako se može implementirati funkcija koja vrši uvećanje svih elemenata nekog segmenta. Njena invarijanta će biti da svi čvorovi u drvetu ili sadrže ažurne vrednosti zbirova ili će biti ispravno obeleženi za kasnija ažuriranja (preko koeficijenta lenje propagacije), a da će nakon njenog izvršavanja koren drveta na kom je funkcija pozvana sadržati aktuelnu vrednost zbira. Nakon početnog obezbeđivanja da vrednost u tekućem čvoru postane ažurna, moguća su tri sledeća slučaja.

• Ako je segment u tekućem čvoru disjunktan u odnosu na segment koji se ažurira, tada su svi čvorovi u poddrvetu kojem je on koren ili već ažurni ili ispravno obeleženi za kasnije ažuriranje i nije potrebno ništa uraditi.

• Ako je segment koji odgovara tekućem čvoru potpuno sadržan u segmentu čiji se elementi uvećavaju, tada se njegova vrednost ažurira (uvećavanjem za \(k \cdot v\), gde je \(k\) broj elemenata segmenta koji odgovara tekućem čvoru, a \(v\) vrednost uvećanja), a njegovoj deci se koeficijent lenje propagacije uvećava za vrednost \(v\).

• Na kraju, ako se ova dva segmenta seku, tada se prelazi na rekurzivnu obradu oba deteta. Nakon izvršavanja funkcije nad njima, sigurni smo da će svi čvorovi u levom i desnom poddrvetu zadovoljavati uslov invarijante i da će koreni i levog i desnog poddrveta imati ažurne vrednosti. Ažurnu vrednost u korenu dobijamo sabiranjem vrednosti njegova dva deteta.

Lenjo segmentno drvo čuvaćemo korišćenjem dva niza: drvo i lenjo: u prvom ćemo čuvati elemente segmentnog drveta, a u drugom koeficijente lenje propagacije svakog od čvorova.

// ažurira elemente lenjog segmentnog drveta koje je smešteno
// u nizove drvo i lenjo od pozicije k u kome se čuvaju zbirovi
// elemenata originalnog niza sa pozicija iz segmenta [x, y]
// nakon što su u originalnom nizu svi elementi sa pozicija iz 
// segmenta [a, b] uvećani za vrednost v
void promeni(vector<int>& drvo, vector<int>& lenjo, int k, int x, int y,
             int a, int b, int v) {
   // ažuriramo vrednost u korenu, ako nije ažurna
   if (lenjo[k] != 0) {
      drvo[k] += (y - x + 1) * lenjo[k];
      // ako nije u pitanju list, propagaciju prenosimo na decu
      if (x != y) {
         lenjo[2*k] += lenjo[k];
         lenjo[2*k+1] += lenjo[k];
      }
      // vrednost u korenu je sad ažurna
      lenjo[k] = 0;
   }
   // ako su intervali disjunktni, ništa nije potrebno raditi
   if (b < x || y < a) return;
   // ako je interval [x, y] ceo sadržan u intervalu [a, b]
   // vrsimo uvecanje cvora za k * v
   if (a <= x && y <= b) {
     drvo[k] += (y - x + 1) * v;
     // ako nije u pitanju list, propagaciju prenosimo na decu
     if (x != y) {
        lenjo[2*k] += v;
        lenjo[2*k+1] += v;
     }
   } else {
     // u suprotnom se intervali seku, 
     // pa rekurzivno obilazimo poddrveta
     int s = (x + y) / 2;
     promeni(drvo, lenjo, 2*k, x, s, a, b, v); 
     promeni(drvo, lenjo, 2*k+1, s+1, y, a, b, v); 
     // azurnu vrednost u korenu dobijamo kao zbir vrednosti dece
     drvo[k] = drvo[2*k] + drvo[2*k+1];
   }
}

// ažurira elemente lenjog segmentnog drveta koje je smešteno
// u nizove drvo i lenjo od pozicije 1 u kome se čuvaju zbirovi
// elemenata originalnog niza sa pozicija iz segmenta [0, n-1]
// nakon što su u originalnom nizu svi elementi sa pozicija iz 
// segmenta [a, b] uvećani za vrednost v
void promeni(vector<int>& drvo, vector<int>& lenjo, int n, 
             int a, int b, int v) {
   promeni(drvo, lenjo, 1, 0, n-1, a, b, v);
}

Složenost funkcije ažuriranja svih elemenata datog segmenta u lenjom segmentnom drvetu iznosi \(O(\log n)\). Naime, kao i u slučaju operacije računanja sume segmenta u segmentnom drvetu, na svakom nivou se razmatra najviše \(4\) čvora, te je maksimalni broj čvorova koji se posećuje jednak \(4\log n\).

Primer 1.4.21. Prikažimo rad ove funkcije na primeru lenjog segmentnog drveta sa slike .

Prikažimo kako bismo sve elemente iz segmenta pozicija \([2, 7]\) uvećali za \(3\).

• Krećemo od korena koji pokriva segment \([0,7]\). Segmenti \([0, 7]\) i \([2, 7]\) se seku, pa stoga ažuriranje prepuštamo deci i nakon njihovog ažuriranja, pri povratku iz rekurzije vrednost korena određujemo kao zbir ažuriranih vrednosti njegove dece.

  • Na levoj strani se segment \([0, 3]\) seče sa segmentom \([2, 7]\) pa i on prepušta ažuriranje naslednicama i ažurira se tek pri povratku iz rekurzije.

    • Segment \([0, 1]\) je disjunktan u odnosu na segment \([2, 7]\) i tu onda nije potrebno ništa raditi.

    • Segment \([2, 3]\) je ceo sadržan u segmentu \([2, 7]\), i za njega direktno znamo kako se zbir uvećava: pošto ovaj čvor pokriva dva elementa i svaki se uvećava za \(3\), zbir ovog segmenta se uvećava ukupno za \(2\cdot 3 = 6\) i postavlja se na \(9\). U ovom trenutku izbegavamo ažuriranje svih vrednosti u drvetu u kom je taj element koren, već samo naslednicima upisujemo da je potrebno propagirati uvećanje za \(3\), ali samu propagaciju odlažemo za trenutak kada ona postane neophodna.

  • U povratku iz rekurzije, vrednost \(10\) ažuriramo i nova vrednost je jednaka \(7+9 = 16\).

  • Što se tiče desnog poddrveta, segment \([4, 7]\) je ceo sadržan u segmentu \([2, 7]\), pa možemo direktno izračunati novu vrednost zbira u ovom čvoru. Naime, pošto se \(4\) elementa uvećavaju za po \(3\), ukupan zbir se uvećava za \(4 \cdot 3 = 12\). Zato se vrednost \(16\) menja u \(16+12=28\). Propagaciju ažuriranja kroz poddrvo sa korenom u ovom čvoru odlažemo i samo njegovoj deci beležimo da je uvećanje za \(3\) potrebno izvršiti u nekom kasnijem trenutku.

• Pri povratku iz rekurzije vrednost u korenu ažuriramo sa \(26\) na \(16 + 28 = 44\).

Nakon izvršavanja ovih operacija dobija se drvo prikazano na slici 2. Ovo lenjo segmentno drvo odgovara nizu \(3,4,4,5,9,8,4,7\).

Pretpostavimo da je u dobijenom segmentnom drvetu potrebno elemente iz segmenta \([0, 5]\) uvećavati za vrednost \(2\).

• Ponovo se kreće od korena lenjog segmentnog drveta i kada se ustanovi da se segment \([0, 7]\) seče sa segmentom \([0, 5]\) ažuriranje se prepušta deci i vrednost u korenu se ažurira tek pri povratku iz rekurzije.

  • Segment \([0, 3]\) je ceo sadržan u segmentu \([0, 5]\), pa se zato vrednost \(16\) uvećava za \(4\cdot 2 = 8\) i postavlja na \(24\). Poddrveta se ne ažuriraju odmah, već se samo njihovim korenima upisuje da je sve vrednosti potrebno ažurirati za \(2\).

  • U desnom poddrvetu segment \([4, 7]\) se seče sa \([0, 5]\), pa se rekurzivno obrađuju poddrveta.

    • Pri obradi čvora sa vrednošću \(11\), primećuje se da je on trebalo da bude ažuriran jer je njegov koeficijent lenje propagacije različit od nula, međutim još nije, pa se najpre njegova vrednost ažurira i uvećava za \(2\cdot 3\) i sa \(11\) menja na \(17\). Njegovi naslednici se ne ažuriraju odmah, već samo ako to bude potrebno i njima se samo upisuje lenja vrednost \(3\).

      Tek nakon toga se primećuje da se segment \([4, 5]\) ceo sadrži u segmentu \([0, 5]\), pa se vrednost \(17\) uvećava za \(2\cdot 2 = 4\) i postavlja na \(21\). Poddrveta se ne ažuriraju odmah, već samo po potrebi tako što se u njihovim korenima postavi vrednost lenjog koeficijenta. Pošto je u njima već upisana vrednost \(3\), ona se sada uvećava za \(2\) i postavlja na \(5\).

    • Sada se prelazi na obradu poddrveta u čijem je korenu vrednost \(5\) i pošto ono nije ažurno, najpre se vrednost \(5\) uvećava za \(2 \cdot 3 = 6\) i postavlja na \(11\), a njegovoj deci se lenji koeficijent postavlja na \(3\).

      Nakon toga se primećuje da je segment \([6,7]\) disjuktan sa \([0, 5]\) i ne radi se ništa.

• U povratku kroz rekurziju se ažuriraju vrednosti roditeljskih čvorova.

Nakon ovih operacija dobija se drvo prikazano na slici 3. Ovo lenjo segmentno drvo odgovara nizu \(5,6,6,7,11,10,4,7\).

Funkcija izračunavanja vrednosti zbira segmenta ostaje praktično nepromenjena, osim što se pri ulasku u svaki čvor vrši njegovo ažuriranje, ako je potrebno. Stoga i njena složenost ostaje nepromenjena i iznosi \(O(\log n)\).

// na osnovu lenjog segmentnog drveta koje je smešteno
// u nizove drvo i lenjo od pozicije k u kome se čuvaju zbirovi
// elemenata polaznog niza sa pozicija iz segmenta [x, y]
// izračunava se zbir elemenata polaznog niza
// sa pozicija iz segmenta [a, b]
int saberi(vector<int>& drvo, vector<int>& lenjo, int k, int x, int y, 
           int a, int b) {
  // ažuriramo vrednost u korenu, ako nije ažurna
  if (lenjo[k] != 0) {
     drvo[k] += (y - x + 1) * lenjo[k];
     if (x != y) {
       lenjo[2*k] += lenjo[k];
       lenjo[2*k+1] += lenjo[k];
     }
     lenjo[k] = 0;
  }
  
  // intervali [x, y] i [a, b] su disjunktni
  if (b < x || a > y) return 0;
  // interval [x, y] je potpuno sadržan unutar intervala [a, b]
  if (a <= x && y <= b)
      return drvo[k];
  // intervali [x, y] i [a, b] se seku
  int s = (x + y) / 2;
  return saberi(drvo, lenjo, 2*k, x, s, a, b) + 
         saberi(drvo, lenjo, 2*k+1, s+1, y, a, b);
}

// na osnovu lenjog segmentnog drveta koje je smešteno
// u nizove drvo i lenjo od pozicije 1 u kome se čuvaju zbirovi
// elemenata polaznog niza sa pozicija iz segmenta [0, n-1]
// izračunava se zbir elemenata polaznog niza sa pozicija
// iz segmenta [a, b]
int saberi(vector<int>& drvo, vector<int>& lenjo, int n, int a, int b) {
  // računamo doprinos celog niza, 
  // tj. elemenata iz intervala [0, n-1]
  return saberi(drvo, lenjo, 1, 0, n-1, a, b);
}

Primetimo da se tokom izvršavanja ove funkcije drvo može menjati, pa argumenti funkcije ne smeju biti konstantni (iako se suštinski vrednosti u drvetu ne menjaju, njegova interna reprezentacija, tj. raspodela podataka između nizova drvo i lenjo se može menjati).

Primer 1.4.22. Prikažimo rad prethodne funkcije na tekućem primeru. Razmotrimo kako se za drvo prikazano na slici 3 izračunava zbir elemenata iz segmenta \([3, 5]\).

• Krećemo od korena drveta koje sadrži sumu segmenta \([0,7]\). Segment \([0, 7]\) se seče sa \([3, 5]\), pa se rekurzivno obrađuju deca.

  • U levom poddrvetu segment \([0, 3]\) takođe ima presek sa \([3, 5]\) pa prelazimo na naredni nivo rekurzije.

    • Prilikom posete čvora u čijem je korenu vrednost \(7\) primećuje se da njegova vrednost nije ažurna, pa se koristi prilika da se ona ažurira, tako što se uveća za \(2\cdot 2=4\) i postaje \(11\), a naslednicima se lenji koeficijent postavlja na \(2\).

      Pošto je segment \([0, 1]\) disjunktan sa \([3, 5]\), vraća se vrednost \(0\).

    • Prilikom posete čvora u čijem je korenu vrednost \(9\) primećuje se da njegova vrednost nije ažurna, pa se koristi prilika da se ona ažurira, tako što se uveća za \(2\cdot 2=4\) i postaje \(13\), a naslednicima se lenji koeficijent uvećava za \(2\), odnosno postaje \(5\).

      Segment \([2, 3]\) se seče sa \([3, 5]\), pa se rekurzivno vrši obrada poddrveta.

      • Vrednost \(1\) se prvo ažurira tako što se poveća za \(1\cdot 5 = 5\) i postaje \(6\), a onda, pošto je \([2, 2]\) disjunktno sa \([3, 5]\) vraća se vrednost \(0\).

      • Vrednost \(2\) se takođe prvo ažurira tako što se poveća za \(1\cdot 5 = 5\) i postaje \(7\), a pošto je segment \([3, 3]\) potpuno sadržan u \([3, 5]\) vraća se vrednost \(7\).

  • U desnom poddrvetu je čvor sa vrednošću \(32\) ažuran, segment \([4, 7]\) se seče sa \([3, 5]\), pa se prelazi na obradu naslednika.

    • Čvor sa vrednošću \(21\) je ažuran, segment \([4, 5]\) je ceo sadržan u \([3, 5]\), pa se vraća vrednost \(21\).

    • Čvor sa vrednošću \(11\) je takođe ažuran, ali je segment \([6, 7]\) disjunktan u odnosu na \([3, 5]\), pa se vraća vrednost \(0\).

• Dakle, čvorovi \(13\) i \(24\) vraćaju vrednost \(7\), čvor \(32\) vraća vrednost \(21\), pa čvor \(56\) vraća vrednost \(7+21=28\).

Dakle, zbir segmenta \([3,5]\) u tekućem drvetu je \(28\). Stanje drveta nakon izvršavanja upita je prikazano na slici 4.

Dakle, u lenjom segmentnom drvetu ne možemo analizom pojedinačnog čvora (npr. lista) zaključiti koja je tačna vrednost tog čvora, međutim, kada nam bude bila potrebna vrednost nekog čvora u drvetu, mi ćemo se od korena spustiti do tog čvora i, idući tom putanjom, sve vrednosti na toj putanji ažurirati. Na taj način, kada budemo stigli do željenog čvora, imaćemo njegovu ažurnu vrednost, što je jedino i važno.