Изменения

Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве.

В такой структуре данных поиск точек в заданном прямоугольнике <tex>(x_{min}, x_{max}) \times (y_{min}, y_{max})</tex> будет выглядеть следующим образом:

# Выберем из дерева поиска те точки, <tex>x</tex>-координата которых лежит в интервале <tex>(x_{min}, x_{max})</tex>. Сделаем это точно так же, как делается [[Реализация запроса в дереве отрезков сверху|запрос сверху в дереве отрезков]]. Из аналогии с деревом отрезков следует, что ответ мы получим в виде <tex>O(\log n)</tex> поддеревьев дерева поиска.