p<>. Putem folosi un arbore de intervale pentru a obtine o complexitate $O(log{~2~} MAXC)$ sau $O(log{~2~} N)$ pentru primele doua operatii si $O(1)$ pentru ce-a de treia. In fiecare nod din arbore retinem de cate ori a fost marcat intervalul respectiv si cate unitati din intervalul respectiv au fost marcate. Primele doua operatii pot fi implementate folosind procedura ACTUALIZARE() iar a treia operatie va returna valoarea numarul de unitati care au fost marcate din radacina arborelui de intervale.

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).

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!
h2. Problema 3

p<>. Se dau $N&le;100 000$ puncte in plan de coordonate numere naturale mai mici ca $2 000 000 000$. Sa se raspunda la $M&le;1 000 000$ intrebari de forma "cate puncte din cele $N$ exista in dreptunghiul cu coltul stanga sus in $(x1,y1)$ si coltul dreapta jos in $(x2,y2)$?".

p<>. Se dau $N&le;100 000$ puncte in plan de coordonate numere naturale mai mici ca $2 000 000 000$. Sa se raspunda la $M&le;1 000 000$ intrebari de forma "cate puncte din cele $N$ exista in dreptunghiul cu coltul stanga sus in $(x{~1~},y{~1~})$ si coltul dreapta jos in $(x{~2~},y{~2~})$?".

p<>. In fisierul $puncte.in$ se vor gasi pe prima linie numerele $N$ si $M$. Pe urmatoarele $N$ linii se vor gasi coordonatele punctelor. Pe urmatoarele $M$ linii se vor gasi cate patru numere naturale reprezentand coordonatele colturilor dreptunghiurilor.

!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<>. 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)$.