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]$.

!arbori-de-intervale?figure3.jpg!

p=. !arbori-de-intervale?figure3.jpg!

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

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

!arbori-de-intervale?figure-8.jpg!

p=. !arbori-de-intervale?figure-8.jpg!

h2. Problema 3

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=. !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 $[y{~1~}, y{~2~}]$ (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!

p=. !arbori-de-intervale?figure7.jpg!

h2. Probleme propuse