Primer 1.4.1. Segmentno drvo kojim se efikasno mogu računati zbirovi segmenata niza \(3, 4, 1, 2, 6, 5, 1, 4\) prikazano je na slici 1.
Jedna struktura podataka koja omogućava prilično jednostavno i efikasno rešavanje prethodno opisanog problema je segmentno drvo (engl. segment tree). Slično kao kod nizova prefiksa, tokom faze pretprocesiranja izračunavaju se zbirovi segmenata polaznog niza, a onda se zbir elemenata proizvoljnog segmenta polaznog niza izražava putem tih unapred izračunatih zbirova. Razlika je to što se ne izračunavaju zbirovi svih prefiksa, već samo posebno odabranih segmenata, kao i to što se zbir proizvoljnog segmenta u opštem slučaju izračunava obradom nekoliko zbirova segmenata (ne samo dva). Segmentna drveta se ne koriste samo za računanje zbira elemenata, već se mogu koristiti i za druge statistike segmenata koje se izračunavaju asocijativnim operacijama (na primer za određivanje proizvoda, najmanjeg ili najvećeg elementa, nzd-a ili nzs-a svih elemenata i slično). Po istom principu definisane su strukture podataka pod nazivom kvad-drveta (engl. quad tree) i okt-drveta (engl. oct tree) koja predstavljaju dvodimenzionalna i trodimenzionalna uopštenja segmentnih dreveta.
Segmentna drveta imaju primenu u oblasti računarske geometrije, za probleme koji se rešavaju tehnikom pokretne prave, kao što je pronalaženje presečnih tačaka između duži u ravni, ispitivanje pripadnosti tačke skupu intervala, izračunavanje površine pokrivene skupom pravougaonika u ravni i sl. Koriste se i u drugim oblastima, poput obrade slika i geografskih informacionih sistema.
Opišimo proces konstrukcije segmentnog drveta. Pretpostavimo da je dužina niza stepen broja \(2\); ako nije, niz se može dopuniti do najbližeg stepena broja \(2\), u slučaju računanja zbirova nulama1. Članovi niza predstavljaju listove drveta. Grupišemo dva po dva susedna čvora i na svakom prethodnom nivou drveta čuvamo roditeljske čvorove koji sadrže zbirove svoja dva deteta.
Primer 1.4.1. Segmentno drvo kojim se efikasno mogu računati zbirovi segmenata niza \(3, 4, 1, 2, 6, 5, 1, 4\) prikazano je na slici 1.
Proverite koliko ste razumeli organizaciju podataka u segmentnom drvetu pomoću sledećeg apleta.
Pošto je drvo potpuno, najjednostavnija implementacija podrazumeva da se čuva implicitno u nizu (slično kao u slučaju hipa). Pretpostavićemo da elemente drveta smeštamo od pozicije \(1\), jer je tada aritmetika sa indeksima malo jednostavnija (elementi polaznog niza mogu biti indeksirani i uobičajeno, krenuvši od nule). Koren se smešta na poziciju \(1\), njegova dva deteta na pozicije \(2\) i \(3\), njihova deca na pozicije \(4\), \(5\), \(6\) i \(7\) itd.
Primer 1.4.2. Drvo iz prethodnog primera se predstavlja sledećim nizom (prvi red sadrži pozicije, a drugi elemente tog niza):
Uočimo nekoliko karakteristika ovog načina smeštanja elemenata drveta. Koren je smešten na poziciji \(1\). Ako polazni niz sadrži \(n\) elemenata, onda se u segmentnom drvetu elementi polaznog niza nalaze se na pozicijama \([n, 2n-1]\). Element koji se u polaznom nizu nalazi na poziciji \(p\), se u segmentnom drvetu nalazi na poziciji \(p+n\). Levo dete čvora na poziciji \(k\) nalazi se na poziciji \(2k\), a desno na poziciji \(2k+1\). Dakle, na parnim pozicijama se nalaze leva deca svojih roditelja, a na neparnim desna. Roditelj čvora \(k\) nalazi se na poziciji \(\lfloor{\frac{k}{2}}\rfloor\).
Primer 1.4.3. Na slici 1 na kojoj je predstavljeno segmentno drvo za niz od 8 elemenata možemo uočiti da se elementi polaznog niza nalaze na pozicijama \([8,15]\). Levo dete čvora sa vrednošću \(10\) koji se nalazi na poziciji \(2\) je čvor sa vrednošču \(7\) koji se nalazi na poziciji \(2\cdot2=4\), a desno dete je čvor sa vrednošću \(3\) koji se nalazi na poziciji \(2\cdot2+1=5\). Roditelj i čvora na poziciji \(4\) i čvora na poziciji \(5\) je čvor koji se nalazi na poziciji \(\lfloor{\frac{4}{2}}\rfloor=\lfloor{\frac{5}{2}}\rfloor=2\).
Proverite koliko ste razumeli organizaciju podataka u segmentnom drvetu pomoću sledećeg apleta.
Formiranje segmentnog drveta na osnovu datog niza je veoma jednostavno.
Najpre se elementi polaznog niza prekopiraju u drvo, krenuvši od pozicije \(n\). Zatim se svi unutrašnji čvorovi drveta (od pozicije \(n-1\), pa unazad do pozicije \(1\)) popunjavaju kao zbirovi svoje dece (na poziciju \(k\) upisujemo zbir elemenata na pozicijama \(2k\) i \(2k+1\)). Korektnost ovog postupka lako se dokazuje indukcijom.
// na osnovu datog niza a dužine n u kom su elementi smešteni od
// pozicije 0 formira se segmentno drvo i elementi mu se smeštaju u
// niz drvo krenuvši od pozicije 1
vector<int> formirajSegmentnoDrvo(const vector<int>& a) {
int n = stepenDvojke(a.size());
vector<int> drvo(2*n, 0);
// kopiramo originalni niz u listove (u niz drvo, od pozicije n nadalje)
copy(begin(a), end(a), next(begin(drvo), n));
// ažuriramo roditelje već upisanih elemenata
for (int k = n-1; k >= 1; k--)
drvo[k] = drvo[2*k] + drvo[2*k+1];
return drvo;
}#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// najmanji stepen dvojke veci ili jednak od n
int stepenDvojke(int n) {
int s = 1;
while (s < n)
s <<= 1;
return s;
}
// na osnovu datog niza a dužine n u kom su elementi smešteni od
// pozicije 0 formira se segmentno drvo i elementi mu se smeštaju u
// niz drvo krenuvši od pozicije 1
vector<int> formirajSegmentnoDrvo(const vector<int>& a) {
int n = stepenDvojke(a.size());
vector<int> drvo(2*n, 0);
// kopiramo originalni niz u listove (u niz drvo, od pozicije n nadalje)
copy(begin(a), end(a), next(begin(drvo), n));
// ažuriramo roditelje već upisanih elemenata
for (int k = n-1; k >= 1; k--)
drvo[k] = drvo[2*k] + drvo[2*k+1];
return drvo;
}
// izračunava se zbir elemenata polaznog niza dužine n koji se
// nalaze na pozicijama iz segmenta [a, b] na osnovu segmentnog drveta
// koje je smešteno u nizu drvo, krenuvši od pozicije 1
int zbirSegmenta(const vector<int>& drvo, int a, int b) {
int n = drvo.size() / 2;
a += n; b += n;
int zbir = 0;
// sve dok je segment neprazan
while (a <= b) {
// ako je levi kraj segmenta desno dete, dodajemo ga posebno u zbir
if (a % 2 == 1) zbir += drvo[a++];
// ako je desni kraj segmenta levo dete, dodajemo ga posebno u zbir
if (b % 2 == 0) zbir += drvo[b--];
// penjemo se na nivo iznad, na roditeljske cvorove
a /= 2;
b /= 2;
}
return zbir;
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije 1
// koje sadrži elemente polaznog niza a dužine n u kom su elementi
// smešteni od pozicije 0, nakon što se na poziciju i polaznog
// niza upiše vrednost v
void upisi(vector<int>& drvo, int i, int v) {
int n = drvo.size() / 2;
// prvo ažuriramo odgovarajući list
int k = i + n;
drvo[k] = v;
// ažuriramo sve roditelje izmenjenih čvorova
for (k /= 2; k >= 1; k /= 2)
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> drvo = formirajSegmentnoDrvo(a);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string upit;
cin >> upit;
if (upit == "p") {
int i, v;
cin >> i >> v >> ws;
upisi(drvo, i, v);
} else if (upit == "z") {
int a, b;
cin >> a >> b;
cout << zbirSegmenta(drvo, a, b) << '\n';
}
}
return 0;
}Složenost ove operacije je očigledno linearna u odnosu na dužinu niza \(n\).
Prethodni pristup formira drvo odozdo naviše (prvo se popune listovi, pa onda unutrašnji čvorovi sve dok se ne dođe do korena).
Još jedan način da se segmentno drvo formira je rekurzivno, odozgo naniže. Iako je ova implementacija komplikovanija i malo neefikasnija (doduše ne asimpotski) usled rekurzivnih poziva, pristup odozgo naniže je u nekim kasnijim operacijama neizbežan, pa ga ilustrujemo na ovom jednostavnom primeru. Svaki čvor drveta predstavlja zbir određenog segmenta pozicija polaznog niza. Segment je jednoznačno određen pozicijom \(k\) u nizu koji odgovara segmentnom drvetu, ali da bismo olakšali implementaciju, granice tog segmenta možemo kroz rekurziju prosleđivati kao parametar funkcije, zajedno sa vrednošću \(k\) (neka je to segment \([x, y]\)). Na slici 2 za svaki čvor segmentnog drveta dat je njegov indeks u odgovarajućem nizu drvo i granice segmenta koje taj čvor pokriva.
Drvo krećemo da gradimo od korena gde je \(k=1\) i \([x,y] = [0, n-1]\). Ako roditeljski čvor pokriva segment \([x, y]\), tada levo dete pokriva segment \([x, \lfloor{\frac{x+y}{2}}\rfloor]\), a desno dete pokriva segment \([\lfloor{\frac{x+y}{2}}\rfloor+1, y]\). Drvo popunjavamo rekurzivno, tako što najpre popunimo levo poddrvo, zatim desno poddrvo i na kraju vrednost u korenu izračunavamo kao zbir vrednosti u levom i desnom detetu. Izlaz iz rekurzije predstavljaju listovi, koje prepoznajemo po tome što pokrivaju segmente dužine \(1\), i u njih samo kopiramo elemente sa odgovarajućih pozicija polaznog niza.
// od elemenata niza a sa pozicija [x, y] formira se segmentno drvo i
// elementi mu se smeštaju u niz drvo krenuvši od pozicije k
void formirajSegmentnoDrvo(const vector<int>& a, vector<int>& drvo,
size_t k, size_t x, size_t y) {
if (x == y)
// u listove prepisujemo elemente polaznog niza
drvo[k] = x < a.size() ? a[x] : 0;
else {
// rekurzivno formiramo levo i desno poddrvo
int s = (x + y) / 2;
formirajSegmentnoDrvo(a, drvo, 2*k, x, s);
formirajSegmentnoDrvo(a, drvo, 2*k+1, s+1, y);
// izračunavamo vrednost u korenu
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
}
// na osnovu datog niza a duzine n u kom su elementi smesteni od
// pozicije 0 formira se segmentno drvo i elementi mu se smeštaju u
// niz drvo krenuvši od pozicije 1
vector<int> formirajSegmentnoDrvo(const vector<int>& a) {
// niz implicitno dopunjujemo nulama tako da mu duzina postane
// najblizi stepen dvojke
int n = stepenDvojke(a.size());
vector<int> drvo(n * 2);
// krećemo formiranje od korena, koji se nalazi u nizu drvo
// na poziciji 1 i pokriva elemente na pozicijama [0, n-1]
formirajSegmentnoDrvo(a, drvo, 1, 0, n - 1);
return drvo;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// od elemenata niza a sa pozicija [x, y] formira se segmentno drvo i
// elementi mu se smeštaju u niz drvo krenuvši od pozicije k
void formirajSegmentnoDrvo(const vector<int>& a, vector<int>& drvo,
size_t k, size_t x, size_t y) {
if (x == y)
// u listove prepisujemo elemente polaznog niza
drvo[k] = x < a.size() ? a[x] : 0;
else {
// rekurzivno formiramo levo i desno poddrvo
int s = (x + y) / 2;
formirajSegmentnoDrvo(a, drvo, 2*k, x, s);
formirajSegmentnoDrvo(a, drvo, 2*k+1, s+1, y);
// izračunavamo vrednost u korenu
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
}
// najmanji stepen dvojke veci ili jednak od n
int stepenDvojke(int n) {
int s = 1;
while (s < n)
s <<= 1;
return s;
}
// na osnovu datog niza a duzine n u kom su elementi smesteni od
// pozicije 0 formira se segmentno drvo i elementi mu se smeštaju u
// niz drvo krenuvši od pozicije 1
vector<int> formirajSegmentnoDrvo(const vector<int>& a) {
// niz implicitno dopunjujemo nulama tako da mu duzina postane
// najblizi stepen dvojke
int n = stepenDvojke(a.size());
vector<int> drvo(n * 2);
// krećemo formiranje od korena, koji se nalazi u nizu drvo
// na poziciji 1 i pokriva elemente na pozicijama [0, n-1]
formirajSegmentnoDrvo(a, drvo, 1, 0, n - 1);
return drvo;
}
// izračunava se zbir onih elemenata polaznog niza, koji se nalaze na
// pozicijama iz segmenta [a, b] i koji se ujedno nalaze u delu
// segmentnog drveta ciji je koren u nizu drvo na poziciji k (taj deo
// drveta pokriva elemente na pozicijama segmenta [x, y] originalnog niza)
int zbirSegmenta(const vector<int>& drvo, int k, int x, int y, int a, int b) {
// segmenti [x, y] i [a, b] su disjunktni
if (b < x || a > y) return 0;
// segment [x, y] je potpuno sadržan unutar segmenta [a, b]
if (a <= x && y <= b)
return drvo[k];
// segmenti [x, y] i [a, b] se seku
int s = (x + y) / 2;
return zbirSegmenta(drvo, 2*k, x, s, a, b) +
zbirSegmenta(drvo, 2*k+1, s+1, y, a, b);
}
// izračunava se zbir elemenata polaznog niza na pozicijama iz
// segmenta [a, b], na osnovu segmentnog drveta smeštenog u nizu drvo
int zbirSegmenta(const vector<int>& drvo, int a, int b) {
int n = drvo.size() / 2;
// krećemo od drveta smeštenog od pozicije 1, koje
// pokriva elemente polaznog niza na pozicijama iz segmenta [0, n-1]
return zbirSegmenta(drvo, 1, 0, n-1, a, b);
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije k,
// koje sadrži elemente polaznog niza a dužine n sa pozicija iz
// segmenta [x, y], nakon što se na poziciju i niza upiše vrednost v
void upisi(vector<int>& drvo, int k, int x, int y, int i, int v) {
if (x == y)
// ažuriramo vrednost u listu
drvo[k] = v;
else {
// proveravamo da li se pozicija i nalazi levo ili desno
// i u zavisnosti od toga ažuriramo odgovarajuće poddrvo
int s = (x + y) / 2;
if (x <= i && i <= s)
upisi(drvo, 2*k, x, s, i, v);
else
upisi(drvo, 2*k+1, s+1, y, i, v);
// pošto se promenila vrednost u nekom od dva poddrveta
// moramo ažurirati vrednost u korenu
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije 1,
// koje sadrži elemente polaznog niza a dužine n u kom su elementi
// smešteni od pozicije 0, nakon što se na poziciju i polaznog
// niza upiše vrednost v
void upisi(vector<int>& drvo, int i, int v) {
int n = drvo.size() / 2;
// krećemo od drveta smeštenog od pozicije 1 koje
// sadrži elemente polaznog niza na pozicijama iz segmenta [0, n-1]
upisi(drvo, 1, 0, n-1, i, v);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> drvo = formirajSegmentnoDrvo(a);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string upit;
cin >> upit;
if (upit == "p") {
int i, v;
cin >> i >> v >> ws;
upisi(drvo, i, v);
} else if (upit == "z") {
int a, b;
cin >> a >> b;
cout << zbirSegmenta(drvo, a, b) << '\n';
}
}
return 0;
}Vremensku složenost prethodne rekurzivne implementacije možemo opisati narednom rekurentnom jednačinom: \(T(n)=2T(n/2)+O(1), T(1)=O(1).\) Njeno rešenje se dobija direktno iz master teoreme i iznosi \(O(n)\), što je isto kao i u slučaju iterativnog formiranja segmentnog drveta.
I zbir elemenata možemo izračunati bilo iterativnim, bilo rekurzivnim postupkom.
Ilustrujmo iterativni postupak (kažemo i postupak odozdo naviše) pomoću nekoliko primera.
Primer 1.4.4. Razmotrimo kako bismo našli zbir elemenata niza \(3, 4, 1, 2, 6, 5, 1, 4\) na pozicijama iz segmenta \([2, 6]\), tj. zbir elemenata \(1, 2, 6, 5\) i \(1\). U segmentnom drvetu taj segment je smešten na pozicijama iz segmenta \([2+8, 6+8] = [10, 14]\) (slika 3). Jasno je da ne treba ići do listova i redom sabirati elemente, već na pametan način iskoristiti već izračunate zbirove segmenata koje se nalaze u drvetu.
Zbir prva dva elementa \(1, 2\) (koji su na pozicijama \(10\) i \(11\)) se nalazi u čvoru iznad njih (na poziciji \(5\)), zbir naredna dva elemenata \(6\) i \(5\) (koji su na pozicijama \(12\) i \(13\)) se nalazi takođe u čvoru iznad njih (na poziciji \(6\)), dok se u roditeljskom čvoru elementa \(1\) (koji je na poziciji \(14\)) nalazi njegov zbir sa elementom \(4\) (koji je na poziciji \(15\) i koji ne pripada segmentu koji sabiramo). Zato zbir elemenata na pozicijama iz segmenta \([10, 14]\) u segmentnom drvetu možemo razložiti na zbir elemenata na pozicijama iz segmenta \([5, 6]\) i elementa na poziciji \(14\) koji odmah zasebno dodajemo na traženi zbir. Na ovaj način penjemo se na nivo iznad tekućeg (dolazimo do roditelja tih čvorova) i nastavljamo postupak računajući zbir elemenata na pozicijama iz segmenta \([5,6]\).
Na poziciji \(5\) nalazi se element \(3\), a na poziciji \(6\) element \(11\). U roditeljskom čvoru elementa \(3\) (na poziciji \(5\)) nalazi se zbir sa elementom levo od njega, koji ne pripada segmentu koji treba da saberemo. Slično, u roditeljskom čvoru elementa \(11\) (na poziciji \(6\)) nalazi se zbir ovog elementa sa elementom desno od njega koji ne pripada segmentu čiji zbir računamo. Stoga oba elementa \(3\) i \(11\) dodajemo zasebno na zbir i ostajemo sa praznim segmentom, čime se postupak računanja zbira datog segmenta završava.
Primer 1.4.5. Razmotrimo kako bismo računali zbir elemenata na pozicijama iz segmenta \([3, 7]\), tj. zbir elemenata \(2, 6, 5, 1, 4\). U segmentnom drvetu taj segment je smešten na pozicijama \([3+8, 7+8] = [11, 15]\).
U roditeljskom čvoru elementa \(2\) (koji je na poziciji \(11\)) nalazi se njegov zbir sa elementom \(1\), levo od njega koji ne pripada segmentu koji sabiramo. Stoga element \(2\) odmah dodajemo na zbir.
Zbirovi elemenata \(6\) i \(5\) (na pozicijama \(12\) i \(13\)) i elemenata \(1\) i \(4\) (na pozicijama \(14\) i \(15\)) se nalaze u čvorovima iznad njih (na pozicijama \(6\) i \(7\)), pa se problem svodi na izračunavanje zbira elemenata na pozicijama \(6\) i \(7\).
Taj zbir je već izračunat, iznosi \(16\) i nalazi se na poziciji \(3\), tako da je samo potrebno da i njega dodamo na zbir.
Dakle, rezultat se dobija sabiranjem elementa \(2\) na poziciji \(11\) i elementa \(16\) na poziciji \(3\).
Generalno, za sve unutrašnje elemente segmenta čiji zbir računamo smo sigurni da se njihov zbir nalazi u čvorovima iznad njih. Jedini izuzetak mogu da budu elementi na krajevima segmenta.
Ako je element na levom kraju segmenta levo dete (što je ekvivalentno tome da se nalazi na parnoj poziciji) tada se u njegovom roditeljskom čvoru nalazi njegov zbir sa elementom desno od njega koji takođe pripada segmentu koji treba sabrati (osim eventualno u slučaju jednočlanog segmenta).
U suprotnom (ako se nalazi na neparnoj poziciji), u njegovom roditeljskom čvoru je njegov zbir sa elementom levo od njega, koji ne pripada segmentu koji sabiramo. U toj situaciji, taj element ćemo posebno dodati na zbir i isključiti iz segmenta koji sabiramo pomoću roditeljskih čvorova.
Ako je element na desnom kraju segmenta levo dete (ako se nalazi na parnoj poziciji), tada se u njegovom roditeljskom čvoru nalazi njegov zbir sa elementom desno od njega, koji ne pripada segmentu koji sabiramo. I u toj situaciji, taj element ćemo posebno dodati na zbir i isključiti iz segmenta koji sabiramo pomoću roditeljskih čvorova.
Konačno, ako se krajnji desni element nalazi u desnom čvoru (ako je na neparnoj poziciji), tada se u njegovom roditeljskom čvoru nalazi njegov zbir sa elementom levo od njega, koji pripada segmentu koji sabiramo (osim eventualno u slučaju jednočlanog segmenta).
// izračunava se zbir elemenata polaznog niza dužine n koji se
// nalaze na pozicijama iz segmenta [a, b] na osnovu segmentnog drveta
// koje je smešteno u nizu drvo, krenuvši od pozicije 1
int zbirSegmenta(const vector<int>& drvo, int a, int b) {
int n = drvo.size() / 2;
a += n; b += n;
int zbir = 0;
// sve dok je segment neprazan
while (a <= b) {
// ako je levi kraj segmenta desno dete, dodajemo ga posebno u zbir
if (a % 2 == 1) zbir += drvo[a++];
// ako je desni kraj segmenta levo dete, dodajemo ga posebno u zbir
if (b % 2 == 0) zbir += drvo[b--];
// penjemo se na nivo iznad, na roditeljske cvorove
a /= 2;
b /= 2;
}
return zbir;
}#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// najmanji stepen dvojke veci ili jednak od n
int stepenDvojke(int n) {
int s = 1;
while (s < n)
s <<= 1;
return s;
}
// na osnovu datog niza a dužine n u kom su elementi smešteni od
// pozicije 0 formira se segmentno drvo i elementi mu se smeštaju u
// niz drvo krenuvši od pozicije 1
vector<int> formirajSegmentnoDrvo(const vector<int>& a) {
int n = stepenDvojke(a.size());
vector<int> drvo(2*n, 0);
// kopiramo originalni niz u listove (u niz drvo, od pozicije n nadalje)
copy(begin(a), end(a), next(begin(drvo), n));
// ažuriramo roditelje već upisanih elemenata
for (int k = n-1; k >= 1; k--)
drvo[k] = drvo[2*k] + drvo[2*k+1];
return drvo;
}
// izračunava se zbir elemenata polaznog niza dužine n koji se
// nalaze na pozicijama iz segmenta [a, b] na osnovu segmentnog drveta
// koje je smešteno u nizu drvo, krenuvši od pozicije 1
int zbirSegmenta(const vector<int>& drvo, int a, int b) {
int n = drvo.size() / 2;
a += n; b += n;
int zbir = 0;
// sve dok je segment neprazan
while (a <= b) {
// ako je levi kraj segmenta desno dete, dodajemo ga posebno u zbir
if (a % 2 == 1) zbir += drvo[a++];
// ako je desni kraj segmenta levo dete, dodajemo ga posebno u zbir
if (b % 2 == 0) zbir += drvo[b--];
// penjemo se na nivo iznad, na roditeljske cvorove
a /= 2;
b /= 2;
}
return zbir;
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije 1
// koje sadrži elemente polaznog niza a dužine n u kom su elementi
// smešteni od pozicije 0, nakon što se na poziciju i polaznog
// niza upiše vrednost v
void upisi(vector<int>& drvo, int i, int v) {
int n = drvo.size() / 2;
// prvo ažuriramo odgovarajući list
int k = i + n;
drvo[k] = v;
// ažuriramo sve roditelje izmenjenih čvorova
for (k /= 2; k >= 1; k /= 2)
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> drvo = formirajSegmentnoDrvo(a);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string upit;
cin >> upit;
if (upit == "p") {
int i, v;
cin >> i >> v >> ws;
upisi(drvo, i, v);
} else if (upit == "z") {
int a, b;
cin >> a >> b;
cout << zbirSegmenta(drvo, a, b) << '\n';
}
}
return 0;
}Pošto se u svakom koraku dužina segmenta \([a, b]\) polovi, a ona je inicijalno sigurno manja ili jednaka \(n\), složenost ove operacije je \(O(\log{n})\).
U narednom apletu možete videti kako se zbir elemenata datog segmenta izračunava odozdo naviše.
✖
Prethodna implementacija vrši izračunavanje odozdo naviše. I za ovu operaciju možemo napraviti rekurzivnu implementaciju koja vrši izračunavanje odozgo naniže. Funkcija kao argument prima čvor drveta (koji je određen pozicijom \(k\) i koji sadrži zbir elemenata na pozicijama iz segmenta \([x, y]\)). U opštem slučaju, neki elementi na pozicijama segmenta \([a, b]\) čiji zbir elemenata računamo su levo od tekućeg čvora, a neki desno (ili su svi levo ili svi desno). Za svaki čvor u segmentnom drvetu funkcija vraća koliki je doprinos segmenta koji odgovara tom čvoru i njegovim naslednicima traženom zbiru elemenata na pozicijama iz segmenta \([a, b]\) u polaznom nizu. Na početku krećemo od korena i računamo doprinos celog drveta zbiru elemenata iz segmenta \([a, b]\). Postoje tri različita moguća odnosa između segmenta \([x, y]\) koji odgovara tekućem čvoru i segmenta \([a,b]\) čiji zbir elemenata tražimo.
Ako su segmenti disjunktni, tj. ako je \(y < a\) ili je \(x > b\), doprinos tekućeg čvora zbiru segmenta \([a, b]\) je nula.
Ako je segment \([x, y]\) u potpunosti sadržan u segmentu \([a, b]\), tj. ako je \(a \leq x\) i \(y \leq b\), tada je doprinos potpun, tj. ceo zbir segmenta \([x, y]\) (a to je broj upisan u nizu na poziciji \(k\)) doprinosi zbiru elemenata na pozicijama iz segmenta \([a, b]\).
U suprotnom, segmenti se seku i tada je doprinos tekućeg čvora jednak zbiru doprinosa njegovog levog i desnog deteta.
Iz ovog razmatranja sledi naredna implementacija.
// izračunava se zbir onih elemenata polaznog niza, koji se nalaze na
// pozicijama iz segmenta [a, b] i koji se ujedno nalaze u delu
// segmentnog drveta ciji je koren u nizu drvo na poziciji k (taj deo
// drveta pokriva elemente na pozicijama segmenta [x, y] originalnog niza)
int zbirSegmenta(const vector<int>& drvo, int k, int x, int y, int a, int b) {
// segmenti [x, y] i [a, b] su disjunktni
if (b < x || a > y) return 0;
// segment [x, y] je potpuno sadržan unutar segmenta [a, b]
if (a <= x && y <= b)
return drvo[k];
// segmenti [x, y] i [a, b] se seku
int s = (x + y) / 2;
return zbirSegmenta(drvo, 2*k, x, s, a, b) +
zbirSegmenta(drvo, 2*k+1, s+1, y, a, b);
}
// izračunava se zbir elemenata polaznog niza na pozicijama iz
// segmenta [a, b], na osnovu segmentnog drveta smeštenog u nizu drvo
int zbirSegmenta(const vector<int>& drvo, int a, int b) {
int n = drvo.size() / 2;
// krećemo od drveta smeštenog od pozicije 1, koje
// pokriva elemente polaznog niza na pozicijama iz segmenta [0, n-1]
return zbirSegmenta(drvo, 1, 0, n-1, a, b);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// od elemenata niza a sa pozicija [x, y] formira se segmentno drvo i
// elementi mu se smeštaju u niz drvo krenuvši od pozicije k
void formirajSegmentnoDrvo(const vector<int>& a, vector<int>& drvo,
size_t k, size_t x, size_t y) {
if (x == y)
// u listove prepisujemo elemente polaznog niza
drvo[k] = x < a.size() ? a[x] : 0;
else {
// rekurzivno formiramo levo i desno poddrvo
int s = (x + y) / 2;
formirajSegmentnoDrvo(a, drvo, 2*k, x, s);
formirajSegmentnoDrvo(a, drvo, 2*k+1, s+1, y);
// izračunavamo vrednost u korenu
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
}
// najmanji stepen dvojke veci ili jednak od n
int stepenDvojke(int n) {
int s = 1;
while (s < n)
s <<= 1;
return s;
}
// na osnovu datog niza a duzine n u kom su elementi smesteni od
// pozicije 0 formira se segmentno drvo i elementi mu se smeštaju u
// niz drvo krenuvši od pozicije 1
vector<int> formirajSegmentnoDrvo(const vector<int>& a) {
// niz implicitno dopunjujemo nulama tako da mu duzina postane
// najblizi stepen dvojke
int n = stepenDvojke(a.size());
vector<int> drvo(n * 2);
// krećemo formiranje od korena, koji se nalazi u nizu drvo
// na poziciji 1 i pokriva elemente na pozicijama [0, n-1]
formirajSegmentnoDrvo(a, drvo, 1, 0, n - 1);
return drvo;
}
// izračunava se zbir onih elemenata polaznog niza, koji se nalaze na
// pozicijama iz segmenta [a, b] i koji se ujedno nalaze u delu
// segmentnog drveta ciji je koren u nizu drvo na poziciji k (taj deo
// drveta pokriva elemente na pozicijama segmenta [x, y] originalnog niza)
int zbirSegmenta(const vector<int>& drvo, int k, int x, int y, int a, int b) {
// segmenti [x, y] i [a, b] su disjunktni
if (b < x || a > y) return 0;
// segment [x, y] je potpuno sadržan unutar segmenta [a, b]
if (a <= x && y <= b)
return drvo[k];
// segmenti [x, y] i [a, b] se seku
int s = (x + y) / 2;
return zbirSegmenta(drvo, 2*k, x, s, a, b) +
zbirSegmenta(drvo, 2*k+1, s+1, y, a, b);
}
// izračunava se zbir elemenata polaznog niza na pozicijama iz
// segmenta [a, b], na osnovu segmentnog drveta smeštenog u nizu drvo
int zbirSegmenta(const vector<int>& drvo, int a, int b) {
int n = drvo.size() / 2;
// krećemo od drveta smeštenog od pozicije 1, koje
// pokriva elemente polaznog niza na pozicijama iz segmenta [0, n-1]
return zbirSegmenta(drvo, 1, 0, n-1, a, b);
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije k,
// koje sadrži elemente polaznog niza a dužine n sa pozicija iz
// segmenta [x, y], nakon što se na poziciju i niza upiše vrednost v
void upisi(vector<int>& drvo, int k, int x, int y, int i, int v) {
if (x == y)
// ažuriramo vrednost u listu
drvo[k] = v;
else {
// proveravamo da li se pozicija i nalazi levo ili desno
// i u zavisnosti od toga ažuriramo odgovarajuće poddrvo
int s = (x + y) / 2;
if (x <= i && i <= s)
upisi(drvo, 2*k, x, s, i, v);
else
upisi(drvo, 2*k+1, s+1, y, i, v);
// pošto se promenila vrednost u nekom od dva poddrveta
// moramo ažurirati vrednost u korenu
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije 1,
// koje sadrži elemente polaznog niza a dužine n u kom su elementi
// smešteni od pozicije 0, nakon što se na poziciju i polaznog
// niza upiše vrednost v
void upisi(vector<int>& drvo, int i, int v) {
int n = drvo.size() / 2;
// krećemo od drveta smeštenog od pozicije 1 koje
// sadrži elemente polaznog niza na pozicijama iz segmenta [0, n-1]
upisi(drvo, 1, 0, n-1, i, v);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> drvo = formirajSegmentnoDrvo(a);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string upit;
cin >> upit;
if (upit == "p") {
int i, v;
cin >> i >> v >> ws;
upisi(drvo, i, v);
} else if (upit == "z") {
int a, b;
cin >> a >> b;
cout << zbirSegmenta(drvo, a, b) << '\n';
}
}
return 0;
}Primer 1.4.6. Razmotrimo kako se ovim pristupom određuje zbir elemenata na pozicijama iz segmenta \([2, 6]\) u originalnom nizu (u segmentnom drvetu ti elementi su na pozicijama \([2+8, 6+8] = [10, 14]\)), prikazan na slici 4.
Izvršavanje kreće od korena. Segment \([0, 7]\) se seče sa segmentom \([2, 6]\) te će zbir biti jednak sumi doprinosa segmenata \([0, 3]\) i \([4, 7]\).
Segment \([0, 3]\) se seče sa segmentom \([2, 6]\) te opet pravimo dva rekurzivna poziva za segmente \([0,1]\) i \([2,3]\).
Segment \([0,1]\) je disjunktan sa segmentom \([2,6]\) pa je njegov doprinos traženoj sumi \(0\).
Segment \([2,3]\) je sadržan u segmentu \([2,6]\) te je njegov doprinos potpun – jednak je vrednosti \(3\) koju taj čvor čuva.
S druge strane, segment \([4, 7]\) se seče sa segmentom \([2, 6]\) te opet pravimo dva rekurzivna poziva za segmente \([4,5]\) i \([6,7]\).
Segment \([4,5]\) je u potpunosti sadržan u segmentu \([2,6]\) te je njegov doprinos potpun i iznosi \(11\).
Segment \([6,7]\) se seče sa segmentom \([2,6]\), pa iz njega startujemo dva rekurzivna poziva: za segmente \([6,6]\) i \([7,7]\).
Segment \([6, 6]\) je u potpunosti sadržan u segmentu čiji zbir računamo, te je njegov doprinos potpun i iznosi \(1\).
Segment \([7, 7]\) je disjunktan sa segmentom čiji zbir računamo, pa je njegov doprinos jednak nula. Dakle, ukupna vrednost sume segmenta biće jednaka \(3+11+1=15\).
U narednom apletu možete videti kako se zbir elemenata datog segmenta izračunava odozgo naniže.
✖
I ova implementacija ima složenost \(O(\log{n})\). Dokažimo to.
Lema 1.4.1. [Broj posećenih čvorova na svakom nivou] Prilikom rekurzivnog obilaska segmentnog drveta, za svaki nivo segmentnog drveta obilaze se najviše po četiri čvora.
Dokaz. Dokažimo ovo tvrđenje principom matematičke indukcije.
Na prvom nivou se posećuje samo jedan čvor, koren drveta, tako da se na ovom nivou posećuje manje od četiri čvora i baza indukcije važi.
Razmotrimo sada proizvoljni nivo drveta: prema induktivnoj hipotezi na njemu se posećuje najviše četiri čvora.
Ako se posećuje najviše dva čvora, u narednom nivou se posećuje najviše četiri čvora jer svaki čvor može da proizvede najviše dva rekurzivna poziva.
Pretpostavimo da se na tekućem nivou posećuju tri ili četiri čvora. Oni mogu biti susedni (slika 4, nivo \(2\)), ali i ne moraju (slika 5, nivo \(3\)). Pošto čvorovi na jednom nivou segmentnog drveta sadrže sume disjunktnih segmenata, jedini čvorovi iz kojih se mogu pokrenuti rekurzivni pozivi su oni koji sadrže granice segmenta čiju sumu računamo (sivi čvorovi na slici): ostali segmenti će biti ili u potpunosti sadržani ili disjunktni sa segmentom čiju sumu računamo (ili zeleni, ili crveni na slici). Stoga, na svakom nivou postoje samo dva čvora iz kojih se mogu napraviti rekurzivni pozivi, tako da će i naredni nivo zadovoljavati polazno tvrđenje. \(\Box\)
Pošto je visina segmentnog drveta \(O(\log{n})\), ukupno se posećuje najviše \(4\log{n}\) čvorova segmentnog drveta, te je složenost operacije izračunavanja zbira segmenta pristupom odozgo naniže takođe \(O(\log{n})\).
I funkciju za ažuriranje segmentnog drveta pri ažuriranju vrednosti nekog elementa polaznog niza možemo implementirati iterativno i rekurzivno.
Prilikom ažuriranja nekog elementa potrebno je ažurirati sve čvorove na putanji od tog lista do korena. S obzirom na to da znamo poziciju roditelja svakog čvora, ova operacija se može veoma jednostavno iterativno implementirati.
Primer 1.4.7. Na slici 6 je na jednom primeru prikazano koje sve čvorove je potrebno ažurirati nakon izmene elementa na poziciji \(2\) u originalnom nizu.
// ažurira segmentno drvo smešteno u niz drvo od pozicije 1
// koje sadrži elemente polaznog niza a dužine n u kom su elementi
// smešteni od pozicije 0, nakon što se na poziciju i polaznog
// niza upiše vrednost v
void upisi(vector<int>& drvo, int i, int v) {
int n = drvo.size() / 2;
// prvo ažuriramo odgovarajući list
int k = i + n;
drvo[k] = v;
// ažuriramo sve roditelje izmenjenih čvorova
for (k /= 2; k >= 1; k /= 2)
drvo[k] = drvo[2*k] + drvo[2*k+1];
}#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// najmanji stepen dvojke veci ili jednak od n
int stepenDvojke(int n) {
int s = 1;
while (s < n)
s <<= 1;
return s;
}
// na osnovu datog niza a dužine n u kom su elementi smešteni od
// pozicije 0 formira se segmentno drvo i elementi mu se smeštaju u
// niz drvo krenuvši od pozicije 1
vector<int> formirajSegmentnoDrvo(const vector<int>& a) {
int n = stepenDvojke(a.size());
vector<int> drvo(2*n, 0);
// kopiramo originalni niz u listove (u niz drvo, od pozicije n nadalje)
copy(begin(a), end(a), next(begin(drvo), n));
// ažuriramo roditelje već upisanih elemenata
for (int k = n-1; k >= 1; k--)
drvo[k] = drvo[2*k] + drvo[2*k+1];
return drvo;
}
// izračunava se zbir elemenata polaznog niza dužine n koji se
// nalaze na pozicijama iz segmenta [a, b] na osnovu segmentnog drveta
// koje je smešteno u nizu drvo, krenuvši od pozicije 1
int zbirSegmenta(const vector<int>& drvo, int a, int b) {
int n = drvo.size() / 2;
a += n; b += n;
int zbir = 0;
// sve dok je segment neprazan
while (a <= b) {
// ako je levi kraj segmenta desno dete, dodajemo ga posebno u zbir
if (a % 2 == 1) zbir += drvo[a++];
// ako je desni kraj segmenta levo dete, dodajemo ga posebno u zbir
if (b % 2 == 0) zbir += drvo[b--];
// penjemo se na nivo iznad, na roditeljske cvorove
a /= 2;
b /= 2;
}
return zbir;
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije 1
// koje sadrži elemente polaznog niza a dužine n u kom su elementi
// smešteni od pozicije 0, nakon što se na poziciju i polaznog
// niza upiše vrednost v
void upisi(vector<int>& drvo, int i, int v) {
int n = drvo.size() / 2;
// prvo ažuriramo odgovarajući list
int k = i + n;
drvo[k] = v;
// ažuriramo sve roditelje izmenjenih čvorova
for (k /= 2; k >= 1; k /= 2)
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> drvo = formirajSegmentnoDrvo(a);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string upit;
cin >> upit;
if (upit == "p") {
int i, v;
cin >> i >> v >> ws;
upisi(drvo, i, v);
} else if (upit == "z") {
int a, b;
cin >> a >> b;
cout << zbirSegmenta(drvo, a, b) << '\n';
}
}
return 0;
}Pošto se \(k\) polovi u svakom koraku petlje, a kreće od vrednosti najviše \(2n-1\), i složenost ove operacije je \(O(\log{n})\).
I ovu operaciju možemo implementirati odozgo naniže.
// ažurira segmentno drvo smešteno u niz drvo od pozicije k,
// koje sadrži elemente polaznog niza a dužine n sa pozicija iz
// segmenta [x, y], nakon što se na poziciju i niza upiše vrednost v
void upisi(vector<int>& drvo, int k, int x, int y, int i, int v) {
if (x == y)
// ažuriramo vrednost u listu
drvo[k] = v;
else {
// proveravamo da li se pozicija i nalazi levo ili desno
// i u zavisnosti od toga ažuriramo odgovarajuće poddrvo
int s = (x + y) / 2;
if (x <= i && i <= s)
upisi(drvo, 2*k, x, s, i, v);
else
upisi(drvo, 2*k+1, s+1, y, i, v);
// pošto se promenila vrednost u nekom od dva poddrveta
// moramo ažurirati vrednost u korenu
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije 1,
// koje sadrži elemente polaznog niza a dužine n u kom su elementi
// smešteni od pozicije 0, nakon što se na poziciju i polaznog
// niza upiše vrednost v
void upisi(vector<int>& drvo, int i, int v) {
int n = drvo.size() / 2;
// krećemo od drveta smeštenog od pozicije 1 koje
// sadrži elemente polaznog niza na pozicijama iz segmenta [0, n-1]
upisi(drvo, 1, 0, n-1, i, v);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// od elemenata niza a sa pozicija [x, y] formira se segmentno drvo i
// elementi mu se smeštaju u niz drvo krenuvši od pozicije k
void formirajSegmentnoDrvo(const vector<int>& a, vector<int>& drvo,
size_t k, size_t x, size_t y) {
if (x == y)
// u listove prepisujemo elemente polaznog niza
drvo[k] = x < a.size() ? a[x] : 0;
else {
// rekurzivno formiramo levo i desno poddrvo
int s = (x + y) / 2;
formirajSegmentnoDrvo(a, drvo, 2*k, x, s);
formirajSegmentnoDrvo(a, drvo, 2*k+1, s+1, y);
// izračunavamo vrednost u korenu
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
}
// najmanji stepen dvojke veci ili jednak od n
int stepenDvojke(int n) {
int s = 1;
while (s < n)
s <<= 1;
return s;
}
// na osnovu datog niza a duzine n u kom su elementi smesteni od
// pozicije 0 formira se segmentno drvo i elementi mu se smeštaju u
// niz drvo krenuvši od pozicije 1
vector<int> formirajSegmentnoDrvo(const vector<int>& a) {
// niz implicitno dopunjujemo nulama tako da mu duzina postane
// najblizi stepen dvojke
int n = stepenDvojke(a.size());
vector<int> drvo(n * 2);
// krećemo formiranje od korena, koji se nalazi u nizu drvo
// na poziciji 1 i pokriva elemente na pozicijama [0, n-1]
formirajSegmentnoDrvo(a, drvo, 1, 0, n - 1);
return drvo;
}
// izračunava se zbir onih elemenata polaznog niza, koji se nalaze na
// pozicijama iz segmenta [a, b] i koji se ujedno nalaze u delu
// segmentnog drveta ciji je koren u nizu drvo na poziciji k (taj deo
// drveta pokriva elemente na pozicijama segmenta [x, y] originalnog niza)
int zbirSegmenta(const vector<int>& drvo, int k, int x, int y, int a, int b) {
// segmenti [x, y] i [a, b] su disjunktni
if (b < x || a > y) return 0;
// segment [x, y] je potpuno sadržan unutar segmenta [a, b]
if (a <= x && y <= b)
return drvo[k];
// segmenti [x, y] i [a, b] se seku
int s = (x + y) / 2;
return zbirSegmenta(drvo, 2*k, x, s, a, b) +
zbirSegmenta(drvo, 2*k+1, s+1, y, a, b);
}
// izračunava se zbir elemenata polaznog niza na pozicijama iz
// segmenta [a, b], na osnovu segmentnog drveta smeštenog u nizu drvo
int zbirSegmenta(const vector<int>& drvo, int a, int b) {
int n = drvo.size() / 2;
// krećemo od drveta smeštenog od pozicije 1, koje
// pokriva elemente polaznog niza na pozicijama iz segmenta [0, n-1]
return zbirSegmenta(drvo, 1, 0, n-1, a, b);
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije k,
// koje sadrži elemente polaznog niza a dužine n sa pozicija iz
// segmenta [x, y], nakon što se na poziciju i niza upiše vrednost v
void upisi(vector<int>& drvo, int k, int x, int y, int i, int v) {
if (x == y)
// ažuriramo vrednost u listu
drvo[k] = v;
else {
// proveravamo da li se pozicija i nalazi levo ili desno
// i u zavisnosti od toga ažuriramo odgovarajuće poddrvo
int s = (x + y) / 2;
if (x <= i && i <= s)
upisi(drvo, 2*k, x, s, i, v);
else
upisi(drvo, 2*k+1, s+1, y, i, v);
// pošto se promenila vrednost u nekom od dva poddrveta
// moramo ažurirati vrednost u korenu
drvo[k] = drvo[2*k] + drvo[2*k+1];
}
}
// ažurira segmentno drvo smešteno u niz drvo od pozicije 1,
// koje sadrži elemente polaznog niza a dužine n u kom su elementi
// smešteni od pozicije 0, nakon što se na poziciju i polaznog
// niza upiše vrednost v
void upisi(vector<int>& drvo, int i, int v) {
int n = drvo.size() / 2;
// krećemo od drveta smeštenog od pozicije 1 koje
// sadrži elemente polaznog niza na pozicijama iz segmenta [0, n-1]
upisi(drvo, 1, 0, n-1, i, v);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> drvo = formirajSegmentnoDrvo(a);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string upit;
cin >> upit;
if (upit == "p") {
int i, v;
cin >> i >> v >> ws;
upisi(drvo, i, v);
} else if (upit == "z") {
int a, b;
cin >> a >> b;
cout << zbirSegmenta(drvo, a, b) << '\n';
}
}
return 0;
}Složenost prethodne implementacije možemo opisati rekurentnom jednačinom: \(T(n)=T(n/2)+O(1), T(1)=O(1)\) i njeno rešenje iznosi \(O(\log{n})\). Naime, dužina intervala \([x, y]\) se u svakom narednom pozivu smanjuje dva puta, a njegova početna dužina je jednaka \(n\).
Umesto funkcije upisi često se razmatra funkcija uvecaj koja element na poziciji i polaznog niza uvećava za datu vrednost v i u skladu sa tim ažurira segmentno drvo. Svaka od ove dve funkcije se jednostavno izražava preko one druge.
Osim za pronalaženje zbira elemenata segmenata, segmentno drvo se može koristiti i za mnoge druge operacije koje imaju svojstvo asocijativnosti. Najčešće su to pronalaženje minimuma ili maksimuma segmenta, NZD ili NZS svih elemenata segmenta i slično. U tim slučajevima se implementacija veoma jednostavno prilagođava tako se na svim mestima u kodu operacija sabiranja menja odgovarajućom binarnom asocijativnom operacijom (min, max, nzd, nzs i slično). Pritom, ako se niz dopunjava do dužine koja je stepen broja \(2\), umesto vrednosti \(0\), koriste se neutralni elementi odgovarajućih operacija (na primer, za min to je vrednost \(+\infty\), za max to je \(-\infty\), za nzd to je \(0\), a za nzs to je \(1\)).
Neke malo naprednije modifikacije omogućavaju i izvršavanje složenijih upita. Na primer, možemo da napravimo drvo koje za svaki segment određuje maksimalnu vrednost tog segmenta i ujedno broj pojavljivanja te maksimalne vrednosti u tom segmentu. Tada se u svakom čvoru čuva par \((m, n)\) sačinjen od te dve vrednosti. Parovi se kombinuju na sledeći način. Ako je vrednost u levom detetu čvora \((m_l, n_l)\), a u desnom \((m_d, n_d)\), tada, ako je \(m_l > m_d\), važi \((m, n) = (m_l, n_l)\), ako je \(m_d > m_l\), važi \((m, n) = (m_d, n_d)\), a ako je \(m_l = m_d\), važi \((m, n) = (m_l, n_l + n_d)\).
Navedimo još neke tipične operacije: određivanje broja elemenata u segmentu koji zadovoljavaju dati uslov (na primer, određivanje broja nula u svakom segmentu ili broja parnih brojeva u svakom segmentu), određivanje pozicije \(k\)-tog po redu elementa u segmentu koji zadovoljava dati uslov, određivanje pozicije prvog elementa u segmentu koji je veći od date vrednosti, određivanje prve pozicije u segmentu niza koji sadrži samo nenegativne vrednosti takve da je zbir prefiksa segmenta do te pozicije veći ili jednak od date vrednosti i slično.
Napomenimo da se neke od ovih operacija mogu realizovati pomoću običnog segmentnog drveta i binarne pretrage tako da im je složenost \(O(\log^2{n})\), a prilagođavanjem segmentnog drveta složenost postaje \(O(\log{n})\). Na primer, u nizu nenegativnih brojeva za dati segment određen pozicijama \([l, d]\), binarnom pretragom intervala \([l, d]\) možemo odrediti najmanju vrednost \(k \in [l, d]\) tako da je zbir prefiksa određenog pozicijama \([l, k]\) veći od date vrednosti \(x\). Binarna pretraga zahteva \(O(\log{(d - l + 1)}) = O(\log{n})\) koraka, a u svakom koraku zbir segmenta određenog pozicijama \([l, k]\) možemo određivati pomoću segmentnog drveta u vremenu \(O(\log{n})\) (jer je prefiks određen pozicijama \([l, k]\) segmenta određenog pozicijama \([l, d]\) ujedno segment originalnog niza). Sa druge strane, možemo definisati rekurzivnu funkciju koja u jednom prolasku kroz segmentno drvo pronalazi traženu vrednost \(k\). Naime, ako je vrednost levog deteta (zbira elemenata u levoj polovini trenutnog segmenta) veća ili jednaka od vrednosti \(x\), onda prefiks rekurzivno tražimo u levom detetu, a ako je manja od vrednosti \(x\), onda u desnom detetu tražimo najkraći prefiks čiji je zbir veći ili jednak od razlike vrednosti \(x\) i vrednosti levog deteta (što je zbir elemenata u levoj polovini trenutnog segmenta). Time se upit izvršava u vremenu \(O(\log{n})\).
Na dopunjena mesta treba upisati neutralni element za operaciju koja sprovodi, tj. element \(n\) koji za svako \(x\) zadovoljava da je \(f(x, n) = x\). Na primer, ako se segmentnim drvetom računaju proizvodi segmenata, niz se može dopuniti do stepena dvojke jedinicama, ako se računa maksimum, niz se može dopuniti vrednostima \(-\infty\), ako se računa minimum niz se može dopuniti vrednostima \(\infty\), ako se računa najveći zajednički delilac, niz se može dopuniti nulama, a ako se računa najmanji zajednički sadržalac, niz se može dopuniti jedinicama.↩︎