Изменения

# Для каждой из промежуточных вершин <tex>v_i</tex> на пути <tex>v_l \to v_n</tex> зафиксируем, из какого ребенка мы поднялись в вершину <tex>v_i</tex>. Если мы поднялись из левого сына, то добавим в искомое множество саму вершину <tex>v_i</tex>, а также множество точек, находящихся в поддереве правого сына вершины <tex>v_i</tex>. Если же мы поднялись из правого сына, то не добавляем ничего.

# Повторим процесс для пути <tex>v_r \to v_n</tex>. Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына.

В итоге, в множество мы добавим <tex>O(\log n)</tex> вершин и <tex>O(\log n)</tex> поддеревьев дерева поиска. Теперь нужно просеять полученное множество — извлечь из него те элементы, <tex>y</tex>-координата которых не находится в прямоугольнике запроса. Для точек это сделать просто — нужно вручную проверить, лежит ли <tex>y</tex>-координата в нужном интервале. Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <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> памяти.