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

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

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

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

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

• Дерево сегментов хранит интервалы и оптимизируется для запросов « какой из этих интервалов содержит заданную точку ».
• В дереве интервалов также хранятся интервалы, но они оптимизированы для запросов « какие из этих интервалов перекрываются с заданным интервалом ». Его также можно использовать для точечных запросов - аналогично сегментному дереву.
• Дерево диапазона хранит точки и оптимизировано для запросов « какие точки попадают в заданный интервал ».
• Двоичное индексированное дерево хранит количество элементов на индекс и оптимизировано для запросов « сколько элементов между индексами 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) пространство

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

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

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

|              | 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

|              | 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 |

Эти таблицы создаются в Github Formatted Markdown - посмотрите этот список, если вы хотите, чтобы таблицы были отформатированы правильно.