Изменения
→Сбалансированное дерево поиска
# Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ.
Каждая из функций <tex>range{\_}search(y_{min}, y_{max})</tex> будет работать в худшем случае за <tex>O(\log n)</tex>, отсюда получаем итоговое время выполнения запроса <tex>O(\log^2 n)</tex>. Что касается памяти, то в сбалансированном дереве поиска <tex>O(\log n)</tex> слоев, а каждый слой содержит массивы, содержащие в сумме ровно <tex>n</tex> точек, соответственно вся структура в целом занимает <tex>O(n\log n)</tex> памяти. Такую структуру данных можно при необходимости обобщить на случай большей размерности.
== Квадро дерево ==
== Инкрементальное квадро дерево ==
