Сегментное дерево - Segment tree

Эта статья посвящена структуре данных, используемых для хранения сегментов. Информацию о структуре данных, используемой для эффективного вычисления сумм префиксов, см. Фенвик дерево.

В Информатика, а дерево сегментов, также известное как дерево статистики, дерево структура данных используется для хранения информации о интервалы, или сегменты. Он позволяет запросить, какой из сохраненных сегментов содержит данную точку. В принципе, это статическая структура; то есть это структура, которую нельзя изменить после постройки. Похожая структура данных - это дерево интервалов.

Сегментное дерево для набора я из п интервалы использует О (п бревно п) хранилище и может быть встроено в О(п бревно п) время. Деревья сегментов поддерживают поиск всех интервалов, содержащих точку запроса в О(бревно п + k), k количество извлеченных интервалов или сегментов.^[1]

Приложения дерева сегментов находятся в областях вычислительная геометрия, и географические информационные системы.

Дерево сегментов можно обобщить на более высокие измерение пробелы.

Описание структуры

В этом разделе описывается структура дерева сегментов в одномерном пространстве.

Позволять S быть набором интервалов или сегментов. Позволять п₁, п₂, ..., п_м - список отдельных конечных точек интервала, отсортированный слева направо. Рассмотрим разбиение вещественной прямой, вызванное этими точками. Области этого разбиения называются элементарные интервалы. Таким образом, элементарные интервалы слева направо:

${displaystyle (-infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],dots ,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+infty )}$

То есть список элементарных интервалов состоит из открытых интервалов между двумя последовательными конечными точками. п_я и п_я+1, чередующиеся с закрытыми интервалами, состоящими из одной конечной точки. Отдельные точки рассматриваются как интервалы, потому что ответ на запрос не обязательно совпадает внутри элементарного интервала и его конечных точек.^[2]

Графический пример структуры дерева сегментов. Этот экземпляр построен для сегментов, показанных внизу.

Учитывая набор я интервалов или сегментов дерева сегментов Т за я имеет следующую структуру:

• Т это двоичное дерево.
• Его листья соответствуют элементарным интервалам, индуцированным концами в я, упорядоченным образом: крайний левый лист соответствует крайнему левому интервалу и т. д. Элементарный интервал, соответствующий листу v обозначается Int (v).
• В внутренние узлы из Т соответствуют интервалам, которые являются союз элементарных интервалов: интервал Int (N), соответствующий узлу N представляет собой объединение интервалов, соответствующих листьям дерева с корнем N. Это означает, что Int (N) - это объединение интервалов двух своих детей.
• Каждый узел или лист v в Т хранит интервал Int (v) и набор интервалов в некоторой структуре данных. Это каноническое подмножество узла v содержит интервалы [Икс, Икс'] из я так что [Икс, Икс'] содержит Int (v) и не содержит Int (parent (v)). То есть каждый узел в Т хранит сегменты, которые охватывают его интервал, но не охватывают интервал его родительского элемента.^[3]

Требования к хранилищу

В этом разделе анализируется стоимость хранения дерева сегментов в одномерном пространстве.

Сегментное дерево Т на съемочной площадке я из п интервалы использует О(п бревно п) место хранения.

Лемма —  Любой интервал [Икс, Икс'] из я хранится в каноническом наборе не более чем для двух узлов на одной глубине.

Доказательство —

Позволять v₁, v₂, v₃ быть тремя узлами на одной глубине, пронумерованными слева направо; и пусть p (v) быть родительским узлом любого заданного узла v. Предполагать [Икс, Икс'] хранится в v₁ и v₃. Это означает, что [Икс, Икс'] охватывает весь интервал от левого конца Int (v₁) до правого конца Int (v₃). Обратите внимание, что все сегменты на определенном уровне не перекрываются и упорядочены слева направо: это верно по конструкции для уровня, содержащего листья, и свойство не теряется при переходе с любого уровня на уровень выше, путем объединения пар смежных сегментов. Теперь любой родитель (v₂) = родитель (v₁), либо первый справа от второго (ребра в дереве не пересекаются). В первом случае Int (parent (v₂)) крайняя левая точка совпадает с Int (v₁крайняя левая точка); во втором случае Int (parent (v₂)) крайняя левая точка находится справа от Int (parent (v₁)) самой правой точки, а значит, и справа от Int (v₁) крайняя правая точка. В обоих случаях Int (parent (v₂)) начинается в или справа от Int (v₁) крайняя левая точка. Аналогичные рассуждения показывают, что Int (parent (v₂)) оканчивается на или слева от Int (v₃) крайняя правая точка. Int (родительский (v₂)) поэтому должны содержаться в [Икс, Икс']; следовательно, [Икс, Икс'] не будет храниться в v₂.

Набор я имеет не более 4п + 1 элементарный интервал. Потому что Т бинарное сбалансированное дерево с не более чем 4п + 1 лист, его высота O (журнал п). Поскольку любой интервал сохраняется не более двух раз на заданной глубине дерева, общий объем памяти равен О(п бревно п).^[4]

Строительство

В этом разделе описывается построение дерева сегментов в одномерном пространстве.

Дерево сегментов из набора сегментов я, можно построить следующим образом. Во-первых, конечные точки интервалов в я отсортированы. Из этого получаются элементарные интервалы. Затем по элементарным интервалам строится сбалансированное двоичное дерево, и для каждого узла v определяется интервал Int (v) это представляет. Осталось вычислить канонические подмножества узлов. Для этого интервалы в я вставляются один за другим в дерево сегментов. Интервал Икс = [Икс, Икс'] можно вставить в поддерево с корнем Т, используя следующую процедуру:^[5]

• Если Int (Т) содержится в Икс затем храните Икс в Т, и закончить.
• Еще:
  • Если Икс пересекает интервал левого дочернего элемента Т, затем вставьте Икс в этом ребенке рекурсивно.
  • Если Икс пересекает интервал правого дочернего элемента Т, затем вставьте Икс в этом ребенке рекурсивно.

Полная строительная операция занимает О(п бревно п) время, п количество сегментов в я.

Доказательство —

Сортировка конечных точек занимает О(п бревно п). Построение сбалансированного двоичного дерева из отсортированных конечных точек занимает линейное время на п.

Вставка интервала Икс = [Икс, Икс'] в дерево стоит O (log п).

Доказательство —

Посещение каждого узла занимает постоянное время (при условии, что канонические подмножества хранятся в простой структуре данных, такой как связанный список ). Когда мы посещаем узел v, мы либо храним Икс в v, или Int (v) содержит конечную точку Икс. Как доказано выше, интервал сохраняется не более двух раз на каждом уровне дерева. Также существует не более одного узла на каждом уровне, чей соответствующий интервал содержит Икс, и один узел, интервал которого содержит Икс'. Таким образом, посещается не более четырех узлов на каждом уровне. Поскольку есть О(бревно п) уровней, общая стоимость вставки составит О(бревно п).^[1]

Запрос

В этом разделе описывается операция запроса дерева сегментов в одномерном пространстве.

Запрос дерева сегментов, получает точку q_Икс(должен быть одним из листьев дерева) и извлекает список всех сохраненных сегментов, содержащих точку q_Икс.

Официально заявлено; учитывая узел (поддерево) v и точка запроса q_Икс, запрос может быть выполнен по следующему алгоритму:

• Сообщите все интервалы в я(v).
• Если v это не лист:
  • Если q_Икс находится в Int (левый дочерний элемент v) тогда
    • Выполните запрос в левом дочернем элементе v.
  • Если q_Икс находится в Int (правый дочерний элемент v) тогда
    • Выполните запрос в правом потомке v.

В дереве сегментов, содержащем п интервалы, те, которые содержат данную точку запроса, могут быть сообщены в О(бревно п + k) время, где k - количество отчетных интервалов.

Доказательство —

Алгоритм запроса посещает один узел на каждом уровне дерева, поэтому О(бревно п) узлов всего. С другой стороны, в узле v, сегменты в я сообщается в О(1 + k_v) время, где k_v это количество интервалов в узле v, сообщил. Сумма всех k_v для всех узлов v посетил, это k, количество отчетных сегментов.^[4]

Обобщение для более высоких измерений

Дерево сегментов может быть обобщено на пространства более высоких измерений в виде многоуровневых деревьев сегментов. В версиях с более высокой размерностью сегментное дерево хранит коллекцию параллельных осям (гипер-) прямоугольников и может извлекать прямоугольники, содержащие заданную точку запроса. В структуре используются О(п бревно^d п) хранилище и отвечает на запросы в О(бревно^d п).

Использование дробное каскадирование уменьшает время запроса, ограниченное логарифмическим коэффициентом. Использование дерево интервалов на самом глубоком уровне связанных структур снижает ограничение памяти на логарифмический фактор.^[6]

Примечания

Запрос, который запрашивает все интервалы, содержащие данную точку, часто называют колющий запрос.^[7]

Дерево сегментов менее эффективно, чем дерево интервалов для запросов диапазона в одном измерении из-за более высоких требований к хранилищу: О(п бревно п) против O (п) интервального дерева. Важность дерева сегментов заключается в том, что сегменты внутри канонического подмножества каждого узла могут быть сохранены любым произвольным образом.^[7]

За п интервалы, конечные точки которых находятся в небольшом целочисленном диапазоне (например, в диапазоне [1,…,О(п)]), оптимальные структуры данных^{[который? ]} существуют с линейным временем предварительной обработки и временем запроса О(1 + k) для сообщения обо всех k интервалы, содержащие заданную точку запроса.

Еще одно преимущество дерева сегментов состоит в том, что его можно легко адаптировать для подсчета запросов; то есть, чтобы сообщить количество сегментов, содержащих данную точку, вместо того, чтобы сообщать сами сегменты. Вместо того, чтобы хранить интервалы в канонических подмножествах, он может просто хранить их количество. Такое дерево сегментов использует линейную память и требует О(бревно п) время запроса, поэтому оно оптимально.^[8]

Версии многомерного дерева интервалов и дерево приоритетного поиска не существует; то есть, нет четкого расширения этих структур, которое решает аналогичную проблему в более высоких измерениях. Но эти структуры можно использовать как связанную структуру деревьев сегментов.^[6]

История

Дерево сегментов было изобретено Джон Бентли в 1977 г .; в «Решениях задач прямоугольника Кли».^[7]

Рекомендации

1. (de Berg et al. 2000 г., п. 227)
2. (de Berg et al. 2000 г., п. 224)
3. (de Berg et al. 2000 г., стр. 225–226).
4. (de Berg et al. 2000 г., п. 226)
5. (de Berg et al. 2000 г., стр. 226–227).
6. (de Berg et al. 2000 г., п. 230)
7. (de Berg et al. 2000 г., п. 229)
8. (де Берг и др. 2000 г., стр. 229–230).

Цитированные источники

• де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк; Шварцкопф, Отфрид (2000). «Больше геометрических структур данных». Вычислительная геометрия: алгоритмы и приложения (2-е изд.). Springer-Verlag Berlin Heidelberg Нью-Йорк. Дои:10.1007/978-3-540-77974-2. ISBN  3-540-65620-0.
• http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf

внешняя ссылка

• Дерево сегментов - CP-алгоритмы