p<>. Un arbore de intervale este un arbore binar echilibrat(diferenta absoluta intre adancimea subarborelui stang si cea a subarborelui drept este cel mult 1). Astfel, adancimea unui arbore de intervale care contine N intervale este $[log{~2~}N]+1$.

[poza]

!arbori-de-intervale?figure2.jpg!

h2. Operatii efectuate asupra unui arbore de intervale:

In figura urmatoare este descrisa structura arborelui de intervale, dupa actualizarea pentru intervalele $[2,2]$, $[6,6]$ si $[9,9]$. Sunt marcate intervalele care conduc la obtinerea numarului de segmente intersectate de primul segment vertical, obtinute in urma interogarii pe intervalul $[0,8]$.

[poza]

!arbori-de-intervale?figure3.jpg!

h2. Problema 2 (Preluata de la IOI 1998, Ziua 2)

|^. 3
3 8 8 3
6 10 12 6

12 4 15 1 |^. 44 | [poza] |

12 4 15 1 |^. 44 | =. !arbori-de-intervale?figure4.jpg! |

Folosind un rationament asemanator ca si la prima problema, constatam necesitatea unui algoritm de baleiere. Vom descompune problema in doua parti: prima data calculam perimetrul folosind doar laturile stanga si dreapta ale dreptunghiurilor pentru a calcula perimetrul pe $OY$; apoi putem sa rotim dreptunghiurile si folosind aceeasi procedura pt a calcula perimetrul pe $OX$, folosind doar laturile sus si jos ale dreptunghiurilor.

p<>. In figura urmatoare este descrisa structura arborelui de intervale, dupa adaugarea intervalelor $[3,8]$ si $[6,10]$ (un interval $[y1,y2]$ reprezinta intervalul de unitati $[y1, y2-1]$ din arbore).

[poza]

!arbori-de-intervale?figure5.jpg!

h2. Problema 3

8 7
8 1
10 10

4 8 9 4 |^. 2 | [poza] |

4 8 9 4 |^. 2 |=. !arbori-de-intervale?figure5.jpg! |

p<>. Problema determinarii numarului de puncte din interiorul unui dreptunghi este o particularizare bidimensionala pentru problema numita in literatura de specialitate "Orthogonal Range Search". Varianta aleasa pentru acest caz consta intr-un arbore de intervale, care permite determinarea numarului de puncte din interiorul unui dreptunghi cu o complexitate $O(log{~2~}^2^ N)$.
p<>. Astfel, se sorteaza coordonatele $x$ ale punctelor si se construieste un arbore de intervale. Primul nivel al arborelui va contine toate coordonatele $x$. Cei doi fii ai lui vor contine prima jumatate, respectiv a doua jumatate a punctelor (sortate dupa coordonata $x$) si asa mai departe. Pentru fiecare interval de coordonate $x$, se mentin sortate coordonatele $y$ corespunzatoare punctelor care au coordonatele $x$ in intervalul respectiv. Astfel, memoria folosita este $O(N*log{~2~} N)$. Pentru a construi efectiv se foloseste o abordare asemanatoare algoritmului de sortare prin interclasare: in fiecare nod, pentru a obtine lista de coordonate $y$ ordonate, se interclaseaza listelele celor doi fii (deja ordonate). Cand se ajunge intr-o frunza, lista nodului este formata dintr-un singur punct.

!arbori-de-intervale?figure6.jpg!
 

p<>. Pentru fiecare dreptunghi, se executa cautarea in arborele de intervale pentru segmentul $[x1, x2]$ (deoarece se folosesc doar cele $N$ coordonate $x$ ale punctelor, se vor potrivi capetele acestui interval folosind cautarea binara la cea mai apropiata coordonata $x$ de fiecare capat). Pentru fiecare interval din arbore atins, se executa doua cautari binare printre coordonatele y corespunzatoare coordonatelor x din acel interval, pentru a determina cate puncte din intervalul respectiv se afla in intervalul $[y1, y2]$ (adica in interiorul dreptunghiului).
p<>. Complexitatea $O(log{~2~}^2^ N)$ poate fi redusa, folosind o metoda descoperita independent de Willard si Lueker in anul $1978$. Se observa ca pentru fiecare coordonata $y$ dintr-un nod, daca presupunem ca se efectueaza o cautare binara, atunci putem determina in timpul interclasarii pozitia din fiecare fiu pe care o va returna cautarea binara pentru aceeasi valoare. Este evident ca pentru o valoare $y$ dintr-un nod care a provenit dintr-un fiu in timpul interclasarii, exista o unica valoare maxima $y'$ din celalalt fiu astfel incat $y'&le;y$. Asadar, tinem pentru fiecare valoare $y$ dintr-un nod doi indici care identifica pozitiile corespunzatoare efectuarii unei cautari binare in fii pentru valoarea $y$. Astfel, in timpul cautarii, in loc sa se efectueze cautari binare, se pot parcurge acesti indici, care ofera in $O(1)$ pozitia in lista cautata, reducand complexitatea totala la $O(log{~2~} N)$.

!arbori-de-intervale?figure7.jpg!