p<>. Fie $MAXC$ valoarea maxima a coordonatelor capetelor de segmente. Folosind un vector pentru a implementa aceste operatiile descrise mai sus vom obtine o complexitate $O(1)$ pentru primele doua operatii si $O(MAXC)$ pentru cea de-a treia. Astfel, complexitatea  va fi $O(N*MAXC)$ in cazul cel mai defavorabil. Putem comprima spatiul $[0...MAXC]$ observand ca doar maxim N din valori din acest interval conteaza, si anume capetele segmentelor orizontale, astfel reducand a treia operatie la $O(N)$, dar algoritmul va avea complexitatea $O(N^2^)$, ceea ce nu aduce nici o imbunatatire fata de algoritmul trivial.

p<>. Aceasta situatie ne indeamna sa cautam o structura de date mai eficienta. O prima varianta ar fi impartirea vectorului in bucati de sqrt(N) reducand complexitatea totala la $O(N*sqrt(N))$. In continuare vom prezenta o structura de date care ofera o complexitate logaritmica pentru operatiile descrise mai sus.

p<>. Aceasta situatie ne indeamna sa cautam o structura de date mai eficienta. O prima varianta ar fi impartirea vectorului in bucati de sqrt(N) reducand complexitatea totala la $O(N*&radic;N)$. In continuare vom prezenta o structura de date care ofera o complexitate logaritmica pentru operatiile descrise mai sus.

h2. Arbori de intervale
Un arbore de intervale este un arbore binar in care fiecare nod poate avea asociata o structura auxiliara(anumite informatii). Dandu-se doua numere intregi $st$ si $dr$, cu $st<dr$, atunci arborele de intervale T(st,dr) se construieste recursiv astfel:

* consideram radacina $nod$ avand asociat intervalul $[st,dr]$
* daca $st<dr$ atunci vom avea asociat subarborele stang T(st,mij), respectiv subarborele drept T(mij+1,dr), unde $mij$ este mijlocul intervalului $[st,dr]$
 
Intervalul $[st,dr]$ asociat unui nod se numeste interval standard. Frunzele arborelui sunt considerate intervale elementare, ele avand lungimea $1$.