Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. <br>Рассмотрим на примере:<br>
[[Файл:ortog_search_tree.png|600px]]<br>
В Рассмотрим, как в такой структуре данных будет выглядеть поиск множества точек , находящихся в заданном прямоугольнике <tex>(x_{min}, x_{max}) \times (y_{min}, y_{max})</tex> будет выглядеть следующим образом:# Выберем из дерева поиска . Для начала, найдем в дереве те точки, <tex>x</tex>-координата которых лежит в интервале <tex>(x_{min}, x_{max})</tex>. Сделаем это точно так жеследующим образом: # Найдем в дереве поиска вершины с минимальной и максимальной <tex>x</tex>-координатой из прямоугольника запроса, добавим их в искомое множество, обозначим их как делается [[Реализация запроса <tex>v_l</tex> и <tex>v_r</tex>. # Добавим в дереве отрезков сверху|запрос сверху искомое множество их наименьшего общего предка <tex>v_n</tex>.# Для каждой из промежуточных вершин <tex>v_i</tex> на пути <tex>v_l \to v_n</tex> зафиксируем, из какого ребенка мы поднялись в дереве отрезков]]вершину <tex>v_i</tex>. Из аналогии с деревом отрезков следуетЕсли мы поднялись из левого сына, то добавим в искомое множество саму вершину <tex>v_i</tex>, а также множество точек, что ответ привязанных к правому сыну вершины <tex>v_i</tex>. Если же мы получим в виде поднялись из правого сына, то не добавляем ничего.# Повторим процесс для пути <tex>O(v_r \log n)to v_n</tex> поддеревьев дерева поиска. Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына.
# Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ.
{{TODO| t=запилить красивую и понятную картинку}}
