Изменения

Для ускорения запроса можно "прошить" дерево поиска, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент <tex>(x, y)</tex> массива-предка соединим с элементами <tex>upper\_bound(y)</tex> и <tex>lower\_bound(y)</tex> каждого массива-ребенка. Ниже представлен пример соединения корня с его левым сыном:<br>[[Файл:ortog_search_tree3.png]]<br>Для выполнения завершающей фазы поиска нам достаточно будет посчитать <tex>upper\_bound()</tex> и <tex>lower\_bound()</tex> только на массиве, привязанному к корню дерева. Для получения границ на других массивах можно будет просто спуститься по ссылкам. Заметим, что все вершины, к массивам которых нужно перейти, смежны с какой-либо из вершин путей <tex>v_l \to v_n</tex> или <tex>v_r \to v_n</tex>. Отсюда следует, что число спусков оценивается как <tex>O(length(v_l \to v_n) + length(v_r \to v_n) = O(\log n)</tex>. Таким образом, поиск теперь будет выполняться за <tex>O(\log^{p-1} n)</tex>, где <tex>p</tex> — размерность пространства.