Asupra unui arbore de intervale se pot face doua operatii semnificative: actualizarea, respectiv interogarea unui interval.

h3. Actualizare unui interval intr-un arbore de intervale

h3. Actualizarea unui interval intr-un arbore de intervale

p<>. Vom prezenta pseudocodul unei proceduri recursive care insereaza un interval $[a, b]$ intr-un arbore de intervale $T(st,dr)$ cu radacina in nodul $nod$. Cea mai eficienta metoda de stocare in memorie a unui arbore de intervale este sub forma unui vector folosind aceeasi codificare a nodurilor precum la heap-uri :

p<>. Vom demonstra in continuare ca operatiile prezentate mai sus au complexitatea $O(log{~2~} N)$ pentru un arbore de $N$ intervale. Este posibil ca intr-un nod sa aiba loc apel atat in fiul stang cat si in cel drept. Acest lucru produce un cost aditional doar prima data cand are loc. Dupa prima "rupere in doua", oricare astfel de "rupere" nu va aduce cost aditional, deoarece unul din fii va fi mereu inclus complet in intervalul $[a, b]$. Cum inaltimea arborelui, pentru $N$ intervale, este $[log{~2~}N] + 1$, complexitatea operatiilor va fi tot $O(log{~2~} N)$.

p<>. Pentru a retine in memorie un arbore de intervale pentru $N$ valori, vom aveam de nevoie de $N + N/2 + N/4 + N/8 + ... = 2*N-1$ locatii de memorie (sunt $2*N-1$ noduri). Deoarece arborele nu este complet, trebuie verificat de fiecare data daca fii unui nod exista in arbore (aceasta verificare a fost omisa in pseudocodul de mai sus), altfel s-ar incerca accesarea de valori din vector care nu exista. Daca memorie disponibila in timpul concursului este suficienta, se poate declara vectorul care retine arborele de intervale de lungime $2^K^$ astfel incat $2^K^ &ge; 2*N-1$, simuland astfel un arbore complet si nefiind necesare verificarile mentionate mai sus.

p<>. Pentru a retine in memorie un arbore de intervale pentru $N$ valori, vom aveam de nevoie de $N + N/2 + N/4 + N/8 + ... = 2*N-1$ locatii de memorie (sunt $2*N-1$ noduri). Deoarece arborele nu este complet, trebuie verificat de fiecare data daca fiii unui nod exista in arbore (aceasta verificare a fost omisa in pseudocodul de mai sus), altfel s-ar incerca accesarea de valori din vector care nu exista. Daca memorie disponibila in timpul concursului este suficienta, se poate declara vectorul care retine arborele de intervale de lungime $2^K^$ astfel incat $2^K^ &ge; 2*N-1$, simuland astfel un arbore complet si nefiind necesare verificarile mentionate mai sus.

p<>. Pentru a rezolva in continuare problema, vom folosi un arbore de intervale pentru a simula in timp logaritmic operatiile facute inainte pe un vector obisnuit. Astfel, in fiecare nod din arborele din intervale vom retine cate capete exista in acel interval. Primele doua operatii vor fi implementate folosind procedura _ACTUALIZARE&#40;&#41;_ de mai sus pentru intervalul $[y, y]$ in arborele $T(0, MAXC)$ si adunand $1$, respectiv scazand $1$ la fiecare nod actualizat. Cea de-a treia operatie poate fi realizata folosind procedura _INTEROGARE&#40;&#41;_ pe intervalul $[y{~1~}, y{~2~}]$. Astfel complexitatea se reduce la $O(N * log{~2~}MAXC)$  Folosind aceeasi tehnica de "comprimare" a coordonatelor se poate obtine o complexitate $O(N * log{~2~}N)$.

3689