Изменения
→Постановка задачи
Пусть дано пространство <math>X</math>, являющееся произведением <math>d</math> линейных порядков:
<math>X = X_1 \times X_2 \times \hdots dotsm \times X_d</math>.
Отрезком в линейно упорядоченном множестве называется множество <math>[a, b] = \{x | a \leq x \leq b\}</math>.
Прямоугольником в пространстве <math>X</math> назовем произведение отрезков из <math>X_1 \hdots dotso X_d</math>:<math>I = [a_1, b_1] \times [a_2, b_2] \times \hdots dotsm \times [a_d, b_d]</math>, где <math>a_i, b_i \in X_i</math>.
Задача состоит в построении динамической структуры данных, хранящей точки пространства <math>X </math> и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
== Одномерный случай ==
* Одномерное range-tree {{---}} просто дерево поиска, описанное выше.
* <math>d</math>-мерное range-tree {{---}} дерево поиска (по первой координате <math>X_1</math>), аналогичное описанному выше, но в каждой вершине дополнительно хранящее <math>d-1</math>-мерное range-tree (по остальным координатам <math>X_2 \times \hdots dotsm \times X_d</math>) для множества элементов, являющихся листами поддерева этой вершины.
Запрос на выдачу точек, принадлежащих некому прямоугольнику, выполняется следующим образом:
