Изменения

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