Изменения

Для ускорения запроса можно "прошить" дерево поиска, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент <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>O(1)</tex>. Таким образом, поиск теперь будет выполняться за <tex>O(\log^{p-1} n)</tex>, где <tex>p</tex> — размерность пространства.