54
правки
Изменения
Новая страница: «{{notready}} Рассмотрим задачу хранения множества точек N-мерного пространства с возможность...»
{{notready}}
Рассмотрим задачу хранения множества точек N-мерного пространства с возможностью перечисления точек, содержащихся в N-мерном прямоугольнике запроса. Эту задачу решает range-tree.
== Постановка задачи ==
Пусть дано пространство <math>X</math>, являющееся произведением <math>N</math> линейных порядков:
<math>X = X_1 \times X_2 \times \hdots \times X_N</math>.
Отрезком в линейно упорядоченном множестве называется множество <math>[a, b] = \{x | a \leq x \leq b\}</math>.
Прямоугольником в пространстве <math>X</math> назовем произведение отрезков из <math>X_1 \hdots X_N</math>:
<math>I = [a_1, b_1] \times [a_2, b_2] \times \hdots \times [a_N, b_N]</math>, где <math>a_i, b_i \in X_i</math>.
Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
Рассмотрим задачу хранения множества точек N-мерного пространства с возможностью перечисления точек, содержащихся в N-мерном прямоугольнике запроса. Эту задачу решает range-tree.
== Постановка задачи ==
Пусть дано пространство <math>X</math>, являющееся произведением <math>N</math> линейных порядков:
<math>X = X_1 \times X_2 \times \hdots \times X_N</math>.
Отрезком в линейно упорядоченном множестве называется множество <math>[a, b] = \{x | a \leq x \leq b\}</math>.
Прямоугольником в пространстве <math>X</math> назовем произведение отрезков из <math>X_1 \hdots X_N</math>:
<math>I = [a_1, b_1] \times [a_2, b_2] \times \hdots \times [a_N, b_N]</math>, где <math>a_i, b_i \in X_i</math>.
Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
