В чем разница между деревьями сегментов, деревьями интервалов, деревьями с двоичным индексом и деревьями диапазонов?

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

  • Ключевая идея / определение
  • Приложения
  • Производительность / заказ в больших размерах / занимаемое пространство

Пожалуйста, не давайте просто определения.


algorithm tree graph-algorithm interval-tree segment-tree
person Aditya    schedule 04.07.2013    source источник
comment
Это не дубликат. Этот вопрос в том, являются ли деревья фенвика обобщением интервальных прядей, и мой вопрос более конкретен и отличается.   -  person Aditya    schedule 04.07.2013
comment
Ответа на него не было получено в stackoverflow .com / questions / 2795989 /, ответ там просто дает определение.   -  person Aditya    schedule 04.07.2013
comment
Как он слишком широкий? В чем разница между x и y? настолько ясен и сфокусирован, насколько это возможно. Это очень хороший вопрос.   -  person IVlad    schedule 04.07.2013
comment
И нигде нет хорошего ответа на этот вопрос. Хороший ответ будет полезен для сообщества   -  person Aditya    schedule 04.07.2013
comment
Большинство этих структур данных (кроме деревьев Фенвика) рассмотрены в этом PDF-файле: Деревья поиска по интервалам, сегментам, диапазонам и приоритетам (автор - Д.Т. Ли). Или вы можете прочитать его как главу из этой книги: Справочник по Структуры данных и приложения.   -  person Evgeny Kluev    schedule 04.07.2013
comment
Не лучший ответ, но все же стоит прочитать quora.com/Data-Structures/   -  person banarun    schedule 04.07.2013
comment
Я прочитал это уже прежде, чем задать вопрос, это не очень хорошо   -  person Aditya    schedule 04.07.2013
comment
Если бы я не знал о TopCoder и др., Этот список выглядел бы довольно случайным. Только деревья сегментов и деревья интервалов имеют одно и то же применение, и отсутствуют несколько структур данных «разделяй и властвуй».   -  person David Eisenstat    schedule 06.07.2013
comment
Деревья поиска по интервалам, сегментам, диапазонам и приоритетам (составленные Д. Т. Ли) были очень полезны.   -  person Sangcheol Choi    schedule 16.08.2013

Ответы (3)


arrow_upward
350
arrow_downward

Все эти структуры данных используются для решения разных задач:

  • Дерево сегментов хранит интервалы и оптимизировано для запросов «какой из этих интервалов содержит данную точку».
  • Дерево интервалов также хранит интервалы, но оптимизировано для запросов «какие из этих интервалов перекрываются с заданным интервалом». Его также можно использовать для точечных запросов - аналогично дереву сегментов.
  • Дерево диапазонов хранит точки и оптимизировано для запросов «какие точки попадают в заданный интервал».
  • Двоичное индексированное дерево хранит количество элементов на каждый индекс и оптимизировано для запросов «сколько элементов находится между индексами m и n».

Производительность / потребление пространства для одного измерения:

  • Дерево сегментов - время предварительной обработки O (n logn), время запроса O (k + logn), пространство O (n logn)
  • Дерево интервалов - время предварительной обработки O (n logn), время запроса O (k + logn), пространство O (n)
  • Дерево диапазонов - время предварительной обработки O (n logn), время запроса O (k + logn), пространство O (n)
  • Двоичное индексированное дерево - время предварительной обработки O (n logn), время запроса O (logn), пространство O (n)

(k - количество полученных результатов).

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

  • Дерево сегментов - интервал можно добавить / удалить за время O (logn) (см. здесь)
  • Дерево интервалов - интервал можно добавить / удалить за время O (logn)
  • Дерево диапазонов - новые точки могут быть добавлены / удалены за время O (logn) (см. здесь)
  • Двоично проиндексированное дерево - количество элементов в индексе может быть увеличено за время O (logn).

Высшие измерения (d> 1):

  • Дерево сегментов - время предварительной обработки O (n (logn) ^ d), время запроса O (k + (logn) ^ d), пробел O (n (logn) ^ (d-1))
  • Дерево интервалов - время предварительной обработки O (n logn), время запроса O (k + (logn) ^ d), пространство O (n logn)
  • Дерево диапазонов - время предварительной обработки O (n (logn) ^ d), время запроса O (k + (logn) ^ d), O (n (logn) ^ (d-1))) пробел
  • Двоичное индексированное дерево - время предварительной обработки O (n (logn) ^ d), время запроса O ((logn) ^ d), пробел O (n (logn) ^ d)
person Lior Kogan    schedule 06.07.2013
comment
У меня действительно сложилось впечатление, что отсюда деревья сегментов ‹интервальные деревья. Есть ли причина предпочесть дерево сегментов? Например. простота реализации? - person j_random_hacker; 25.07.2013
comment
@j_random_hacker: Алгоритмы на основе деревьев сегментов имеют преимущества в некоторых более сложных многомерных вариантах запроса интервалов. Например, определение того, какие линейные сегменты, не параллельные оси, пересекаются с 2D-окном. - person Lior Kogan; 25.07.2013
comment
Спасибо, мне было бы интересно узнать, что вы могли бы дать по этому поводу. - person j_random_hacker; 26.07.2013
comment
@j_random_hacker, деревья сегментов имеют еще одно интересное применение: RMQ (минимальный диапазон запросов) за время O (журнал N), где N - общий размер интервала. - person ars-longa-vita-brevis; 26.02.2014
comment
@LiorKogan Сегментные деревья должны занимать O (n) только в одном измерении, если они реализованы правильно. Используйте массив размером 2 * n. - person Nicholas Pipitone; 21.06.2016
comment
@NicholasPipitone: это верно, когда вы используете дерево сегментов для поиска сумм заданного диапазона. Для интервальных запросов, как обсуждалось выше, вам сначала нужно отсортировать интервалы по их конечным точкам. - person Lior Kogan; 26.06.2016
comment
Может быть, можно построить одномерное двоичное индексированное дерево за O (n)? stackoverflow.com/questions/31068521/ - person Thilo; 13.06.2017
comment
Я думаю, B+ tree может делать то же самое, что Range и binary indexed tree. Я прав? Он также может делать то, что может делать дерево интервалов / сегментов, но может быть не таким эффективным. - person M.kazem Akhgary; 07.02.2018
comment
В чем разница между 2d R-деревом и 2d сегментным деревом? - person shuva; 14.06.2018
comment
Я также слышал, что interval-trees сбалансированы и более сжаты, чем segment trees. Лучше ли это дерево сегментов, чем автономное дерево и дерево интервалов, быть более интерактивным (где выполняется больше вставок). - person shuva; 14.06.2018
comment
Почему сегментные деревья занимают O (n log n) пространство? Они хранят N листьев + N / 2 + N / 4 + ... + N / 2 ^ (log N), и эта сумма равна O (N), если я не ошибаюсь. Также ответ @ icc97 также сообщает о пространстве O (N). - person Ant; 19.06.2018
comment
@LiorKogan Спасибо - я прочитал комментарий, но я не уверен, как необходимость держать вещи в порядке приведет к увеличению сложности пространства - я был бы признателен, если бы вы могли подробнее рассказать об этом! :-) - person Ant; 19.06.2018
comment
@Ant: см. en.wikipedia.org/wiki/Segment_tree#Storage_requirements - person Lior Kogan; 19.06.2018
comment
@j_random_hacker: см., например, cs.yazd. ac.ir/farshi/Teaching/CG3921/Slides/ - person Lior Kogan; 19.06.2018
comment
Раньше я думал, что RMQ (запрос минимального / максимального диапазона) и запрос суммы диапазона являются основным приложением для дерева сегментов ._. - person hashlash; 30.10.2019

arrow_upward
28
arrow_downward

Не то чтобы я мог добавить что-нибудь к ответу Лиора, но похоже, что это можно сделать с хорошей таблицей.

Одно измерение

k - количество полученных результатов

Operation Segment Interval Range Indexed
Preprocessing n logn n logn n logn n logn
Query k+logn k+logn k+logn logn
Space n logn n n n
Insert/Delete logn logn logn logn

Высшие измерения

d > 1

Operation Segment Interval Range Indexed
Preprocessing n(logn)^d n logn n(logn)^d n(logn)^d
Query k+(logn)^d k+(logn)^d k+(logn)^d (logn)^d
Space n(logn)^(d-1) n logn n(logn)^(d-1)) n(logn)^d
person icc97    schedule 09.01.2016
comment
Что вы имеете в виду под сообщенными результатами? - person Pratik Singhal; 01.02.2016
comment
Алгоритмы поиска @ ps06756 часто имеют время выполнения log (n), где n - это входной размер, но могут давать результаты, линейные по n, что не может быть выполнено за логарифмическое время (вывод n чисел в log (n) времени невозможен) . - person oerpli; 23.08.2016
comment
Разве в первой таблице дерева сегментов не должно быть O(n logn) space? - person Danny_ds; 23.11.2018

arrow_upward
0
arrow_downward

Границы для предварительной обработки и пространства для деревьев сегментов и двоичных индексированных деревьев могут быть улучшены:

person Asad-ullah Khan    schedule 21.03.2021