Pentru a reprezenta $n$ puncte de coordonate intregi in plan cu ajutorul structurii de _QuadTree_, vom insera care un punct pe rand in _QuadTree_. Pornim de la un _QuadTree_ gol si inseram un nod recursiv, vedem pentru fiecare patrat care nu are latura de dimensiune unu in care din cele patru patrate din interiorul lui intra punctul nostru. Daca nu exista nod care sa reprezinte acel patrat, il creem noi.

Avantajul pentru structura de _QuadTree_ este usurinta implementarii, dezavantajul este ca structura lui si timpul de raspuns la intrebari depind si de configuratia punctelor, nu numai de numarul total de puncte.

Avantajul pentru structura de _QuadTree_ este usurinta implementarii, dezavantajul este ca structura lui si timpul de raspuns la intrebari depind si de configuratia punctelor, nu numai de numarul total de puncte.
 
h2. kD-Tree
 
_kD-Tree_ este o structura de date care organizeaza o multime de puncte in $k$ dimensiuni, imparte spatiul in semispatii astfel ca fiecare nod din arbore reprezinta un paralelipiped si contine in el un punct. Noi suntem interesati de arbori 2D in special. Pentru cazul 2D, primului nod ii va fi asociat intreg planul. Se duce o linie verticala de abscisa $x$ care imparte planul in doua si punctele in doua multimi de cardinal egal. Subarborele din stanga va contine toate punctele din stanga acestei drepte verticale, iar subarborele din dreapta va contine toate punctele din dreapta acestei drepte verticale. Radacinei arborelui din stanga ii va fi asociat semiplanul stang determinat de dreapta verticala, si va contine punctul median dintre punctele din semiplanul stang sortate dupa $y$. Astfel, la nivel impar punctele vor fi mediane din sirul punctelor sortat dupa $x$, iar la nivel par punctele vor fi mediane din sirul punctelor sortat dupa $y$. Pentru mai multe dimensiuni ale spatiului ciclam dupa $d{~1~}$, $d{~2~}$,..., $d{~n~}$ si apoi iar $d{~1~}$ ca sa punem elementul median pe nivelul curent. In cazul 2D complexitatea crearii unui asemenea arbore e O(n log n). Pentru a raspunde la query-uri pe un dreptunghi coboram in arbore in fii pentru care domeniul asociat se intersecteaza cu dreptunghiul nostru. Se poate demonstra ca aceasta operatie are timpul de executie in cel mai rau caz O(sqrt(n)).