Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{notready}}
 
{{notready}}
  
Рассмотрим задачу хранения множества точек N-мерного пространства с возможностью перечисления точек, содержащихся в N-мерном прямоугольнике запроса. Эту задачу решает range-tree.
+
Рассмотрим задачу хранения множества точек d-мерного пространства с возможностью перечисления точек, содержащихся в d-мерном прямоугольнике запроса. Эту задачу решает range-tree.
  
 
== Постановка задачи ==
 
== Постановка задачи ==
  
Пусть дано пространство <math>X</math>, являющееся произведением <math>N</math> линейных порядков:
+
Пусть дано пространство <math>X</math>, являющееся произведением <math>d</math> линейных порядков:
<math>X = X_1 \times X_2 \times \hdots \times X_N</math>.
+
<math>X = X_1 \times X_2 \times \hdots \times X_d</math>.
  
 
Отрезком в линейно упорядоченном множестве называется множество <math>[a, b] = \{x | a \leq x \leq b\}</math>.
 
Отрезком в линейно упорядоченном множестве называется множество <math>[a, b] = \{x | a \leq x \leq b\}</math>.
  
Прямоугольником в пространстве <math>X</math> назовем произведение отрезков из <math>X_1 \hdots X_N</math>:
+
Прямоугольником в пространстве <math>X</math> назовем произведение отрезков из <math>X_1 \hdots X_d</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>.
+
<math>I = [a_1, b_1] \times [a_2, b_2] \times \hdots \times [a_d, b_d]</math>, где <math>a_i, b_i \in X_i</math>.
  
 
Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
 
Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
Строка 17: Строка 17:
 
== Одномерный случай ==
 
== Одномерный случай ==
  
Для начала рассмотрим задачу в случае <math>N = 1</math>.
+
Для начала рассмотрим задачу в случае <math>d = 1</math>.
  
 
Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.
 
Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.
Строка 42: Строка 42:
  
 
* Одномерное range-tree {{---}} просто дерево поиска, описанное выше.
 
* Одномерное range-tree {{---}} просто дерево поиска, описанное выше.
* <math>N</math>-мерное range-tree {{---}} дерево поиска (по первой координате <math>X_1</math>), аналогичное описанному выше, но в каждой вершине дополнительно хранящее <math>N-1</math>-мерное range-tree (по остальным координатам <math>X_2 \times \hdots \times X_N</math>) для множества элементов, являющихся листами поддерева этой вершины.
+
* <math>d</math>-мерное range-tree {{---}} дерево поиска (по первой координате <math>X_1</math>), аналогичное описанному выше, но в каждой вершине дополнительно хранящее <math>d-1</math>-мерное range-tree (по остальным координатам <math>X_2 \times \hdots \times X_d</math>) для множества элементов, являющихся листами поддерева этой вершины.
  
 
Запрос на выдачу точек, принадлежащих некому прямоугольнику, выполняется следующим образом:
 
Запрос на выдачу точек, принадлежащих некому прямоугольнику, выполняется следующим образом:
Строка 52: Строка 52:
  
 
Таким образом, алгоритм сначала найдет по первой координате некоторый набор поддеревьев, потом выполнит поиск по второй координате внутри этих поддеревьев, и так далее.
 
Таким образом, алгоритм сначала найдет по первой координате некоторый набор поддеревьев, потом выполнит поиск по второй координате внутри этих поддеревьев, и так далее.
 +
 +
== Оценка времени работы и потребляемой памяти ==
 +
 +
Фаза алгоритма, обрабатывающая одну координату, может выдать <math>O(\log n)</math> поддеревьев высотой <math>O(\log n)</math>, каждое из которых будет обработано фазой по следующей координате, и т.д. Таким образом, время запроса - <math>O(\log^d n + k)</math>, где k - размер ответа (количество точек ответа).
 +
 +
Докажем по индукции оценку в <math>O(n \log^{d-1} n)</math> для потребляемой памяти для структуры range-tree.
 +
 +
<math>d = 1</math>: в одномерном случае range-tree является обычным деревом, оценка в <math>O(n \log^0 n) = O(n)</math> очевидна.
 +
 +
<math>d > 1</math>: очевидно, что основным слагаемым в оценке потребляемой памяти будут не сами хранимые элементы, а range-tree меньшей размерности, хранимые в каждой вершине, которые по индукционному предположению занимают <math>O(n \log^{d-2} n)</math> памяти. Просуммируем размеры этих range-tree (суммирование по расстоянию до вершины от корня):
 +
<math>\sum_{k=1}^{\log n} 2^k O(\frac{n}{2^k} \log^{d-2} \frac{n}{2^k}) = \sum_{k=1}^{\log n} O(n \log^{d-2} n) = O(n \log^{d-1} n)</math>. QED.

Версия 11:52, 16 января 2014

Конспект не готов.

Рассмотрим задачу хранения множества точек d-мерного пространства с возможностью перечисления точек, содержащихся в d-мерном прямоугольнике запроса. Эту задачу решает range-tree.

Постановка задачи

Пусть дано пространство [math]X[/math], являющееся произведением [math]d[/math] линейных порядков: [math]X = X_1 \times X_2 \times \hdots \times X_d[/math].

Отрезком в линейно упорядоченном множестве называется множество [math][a, b] = \{x | a \leq x \leq b\}[/math].

Прямоугольником в пространстве [math]X[/math] назовем произведение отрезков из [math]X_1 \hdots X_d[/math]: [math]I = [a_1, b_1] \times [a_2, b_2] \times \hdots \times [a_d, b_d][/math], где [math]a_i, b_i \in X_i[/math].

Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.

Одномерный случай

Для начала рассмотрим задачу в случае [math]d = 1[/math].

Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.

Будем использовать сбалансированное бинарное дерево поиска, в листьях которого будем хранить точки искомого множества, а в нелистовых вершинах - разделющие значения, по которым будет вестись поиск в дереве.

Запрос задачи в одномерном случае превращается в перечисление множества значений, лежащих в отрезке запроса [math][a, b][/math].

Алгоритм, перечисляющий элементы дерева, входящие в отрезок запроса:

  • Запустить обычный поиск в двоичном дереве элементов [math]a[/math] и [math]b[/math], остановившись в последней общей вершине пути из корня; назовем эту вершину [math]v[/math].
  • Продолжить поиск элемента [math]a[/math] из вершины [math]v[/math]. При этом при каждом переходе к левому ребенку добавлять правое поддерево текущей вершины к ответу. Проверить последнюю вершину (лист) на вхождение в отрезок запроса и в случае необходимости добавить лист в ответ.
  • Аналогично, продолжить поиск элемента [math]b[/math] из вершины [math]v[/math]. При каждом переходе к правому ребенку добавлять левое поддерево к ответу. Аналогично проверить последнюю вершину в пути.

Здесь "добавить поддерево к ответу" означает пройти по поддереву целиком и каждый лист добавить к ответу.

Несложно понять, что описанный алгоритм действительно решает поставленную задачу за время [math]O(\log n + k)[/math], где [math]n[/math] - количество элементов в дереве, [math]k[/math] - размер ответа.

Многомерный случай

Теперь рассмотрим общий, многомерный случай задачи. Для её решения будем использовать структуру данных под названием range-tree.

Дадим следующее рекурсивное определение range-tree:

  • Одномерное range-tree — просто дерево поиска, описанное выше.
  • [math]d[/math]-мерное range-tree — дерево поиска (по первой координате [math]X_1[/math]), аналогичное описанному выше, но в каждой вершине дополнительно хранящее [math]d-1[/math]-мерное range-tree (по остальным координатам [math]X_2 \times \hdots \times X_d[/math]) для множества элементов, являющихся листами поддерева этой вершины.

Запрос на выдачу точек, принадлежащих некому прямоугольнику, выполняется следующим образом:

  • Выполнить описанную выше процедуру поиска элементов отрезка для проекции прямоугольника запроса на [math]X_1[/math].
  • При добавлении поддерева к ответу:
    • Если текущая координата - последняя, выдать все листы поддерева в качестве ответа
    • Если текущая координата - не последняя, перейти к сохраненному в корне поддерева range-tree по следующим координатам и повторить тот же алгоритм.

Таким образом, алгоритм сначала найдет по первой координате некоторый набор поддеревьев, потом выполнит поиск по второй координате внутри этих поддеревьев, и так далее.

Оценка времени работы и потребляемой памяти

Фаза алгоритма, обрабатывающая одну координату, может выдать [math]O(\log n)[/math] поддеревьев высотой [math]O(\log n)[/math], каждое из которых будет обработано фазой по следующей координате, и т.д. Таким образом, время запроса - [math]O(\log^d n + k)[/math], где k - размер ответа (количество точек ответа).

Докажем по индукции оценку в [math]O(n \log^{d-1} n)[/math] для потребляемой памяти для структуры range-tree.

[math]d = 1[/math]: в одномерном случае range-tree является обычным деревом, оценка в [math]O(n \log^0 n) = O(n)[/math] очевидна.

[math]d \gt 1[/math]: очевидно, что основным слагаемым в оценке потребляемой памяти будут не сами хранимые элементы, а range-tree меньшей размерности, хранимые в каждой вершине, которые по индукционному предположению занимают [math]O(n \log^{d-2} n)[/math] памяти. Просуммируем размеры этих range-tree (суммирование по расстоянию до вершины от корня): [math]\sum_{k=1}^{\log n} 2^k O(\frac{n}{2^k} \log^{d-2} \frac{n}{2^k}) = \sum_{k=1}^{\log n} O(n \log^{d-2} n) = O(n \log^{d-1} n)[/math]. QED.