AtomKrieg: пример про двумерный случай range tree, здесь (1,2) - это точка пространства RxR, с первой координатой 1, в второй 2. А не интервал из R. То есть вопрос: три точки на плоскости, у которых совпадают первые координаты. Как построить range tree?
Николай: Получилось так: сначала нужно создать АВЛ-дерево из чисел последовательности, а потом, не балансируя, добавить эти числа ещё раз в дерево, как в дерево поиска. Они как раз станут листами, это нетрудно доказать. Получается сбалансированное дерево, в листах которого заданные числа. Спасибо большое!