daca (a <= mij) atunci ACTUALIZARE(2*nod, st, mij, a, b)
      daca (b > mij) atunci ACTUALIZARE(2*nod+1, mij+1, dr, a, b)
      actualizeaza structura auxiliara din nodul nod

==
 
h3. Interogarea unui interval intr-un arbore de intervale
 
p<>. Vom prezenta pseudocodul unei proceduri recursive care returneaza informatiile asociate unui interval $[a,b]$ intr-un arbore de intervale T(st,dr) cu radacina in nodul $nod$.
 
==code(c) |
procedura INTEROGARE(nod, st, dr, a, b)
   daca (a<=st) si (dr<=b) atunci
      returneaza structura auxiliara din nod
   altfel
      mij = (st+dr)/2
      daca (a <= mij) atunci INTEROGARE(2*nod, st, mij, a, b)
      daca (b > mij) atunci INTEROGARE(2*nod+1, mij+1, dr, a, b)
      returneaza structura auxiliara din fiul stang combinata cu cea din fiul drept
==
 
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)$.

==