h3. Solutie $O(N*logN)$
Solutia prezentata poate fi optimizata la complexitate $O(N*logN)$, folosind o tehnica standard. Orice query de acest tip corespunzator unui arbore de intervale 2D poate fi redus de la o complexitate $O(log^2^N)$ la o complexitate $O(log N)$. Practic, se va efectua o cautare binara a coordonatei $Y$ inferioare si superioare numai in cadrul radacinii arborelui de intervale. Apoi, din constructia arborelui, vom memora pentru fiecare punct $P$ al fiecarui nod, $4$ pointeri:

* un pointer catre punctul cu cea mai mica coordonata $Y$ mai mare sau egala cu cea a punctului $P$ si care se afla in intervalul de coordonate $X$ al fiului stanga
* un pointer catre punctul cu cea mai mica coordonata $Y$ mai mare sau egala cu cea a punctului $P$ si care se afla in intervalul de coordonate $X$ al fiului dreapta
* un pointer catre punctul cu cea mai mare coordonata $Y$ mai mica sau egala cu cea a punctului $P$ si care se afla in intervalul de coordonate $X$ al fiului stanga