Мы представили дерево сегментов с простым примером в предыдущем посте. В этом посте проблема Range Minimum Query обсуждается как еще один пример, где можно использовать дерево сегментов. Ниже приводится постановка проблемы.
У нас есть массив arr [0. , , н-1]. Мы должны быть в состоянии эффективно найти минимальное значение от индекса qs (начало запроса) до qe (конец запроса), где 0 <= qs <= qe <= n-1 .
Простое решение — запустить цикл от qs до qe и найти минимальный элемент в заданном диапазоне. Это решение занимает O (n) время в худшем случае.
Другое решение заключается в создании двумерного массива, в котором запись [i, j] хранит минимальное значение в диапазоне arr [i..j]. Минимум заданного диапазона теперь можно рассчитать за время O (1), но предварительная обработка занимает время O (n ^ 2). Кроме того, этот подход требует O (n ^ 2) дополнительного пространства, которое может стать огромным для больших входных массивов.
Сегментное дерево может использоваться для предварительной обработки и запроса в умеренное время. Для дерева сегментов время предварительной обработки равно O (n), а время для минимального диапазона запроса равно O (Logn). Требуется дополнительное пространство O (n) для хранения дерева сегментов.
Представление Сегментных деревьев
1. Конечные узлы являются элементами входного массива.
2. Каждый внутренний узел представляет минимум всех листьев под ним.
Представление массива дерева используется для представления деревьев сегментов. Для каждого узла по индексу i левый потомок имеет индекс 2 * i + 1, правый потомок — 2 * i + 2, а родительский — ,
Построение дерева сегментов из заданного массива
Начнем с сегмента arr [0. , , н-1]. и каждый раз, когда мы делим текущий сегмент на две половины (если он еще не стал сегментом длины 1), а затем вызываем одну и ту же процедуру для обеих половин, и для каждого такого сегмента мы сохраняем минимальное значение в дереве сегментов. узел.
Все уровни построенного дерева сегментов будут полностью заполнены, кроме последнего уровня. Кроме того, дерево будет полным двоичным деревом, потому что мы всегда делим сегменты на две половины на каждом уровне. Поскольку построенное дерево всегда является полным двоичным деревом с n листьями, будет иметься n-1 внутренних узлов. Таким образом, общее количество узлов будет 2 * n — 1.
Высота сегмента дерева будет , Поскольку дерево представлено с использованием массива, и необходимо поддерживать связь между родительскими и дочерними индексами, объем памяти, выделенной для дерева сегментов, будет
,
Запрос минимального значения заданного диапазона
Как только дерево построено, как сделать минимальный диапазон запроса, используя построенное дерево сегментов. Ниже приводится алгоритм, чтобы получить минимум.
// qs --> query start index, qe --> query end index int RMQ(node, qs, qe) { if range of node is within qs and qe return value in node else if range of node is completely outside qs and qe return INFINITE else return min( RMQ(node's left child, qs, qe), RMQ(node's right child, qs, qe) ) }
Реализация:
|
С
|
Джава
|
python3
|
C #
|
Выход:
Minimum of values in range [1, 5] is = 2
Сложность времени:
Сложность времени для построения дерева O (n). Всего существует 2n-1 узлов, и значение каждого узла вычисляется только один раз при построении дерева.
Временная сложность запроса составляет O (Logn). Чтобы запросить минимум диапазона, мы обрабатываем не более двух узлов на каждом уровне, и количество уровней равно O (Logn).
Пожалуйста, перейдите по следующим ссылкам, чтобы найти больше решений для определения минимальной проблемы запроса.
http://espressocode.top/range-minimum-query-for-static-array/
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_(RMQ)
http://wcipeg.com/wiki/Range_minimum_query
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Итеративное дерево сегментов (минимальный диапазон запросов)
- Сегментное дерево | Установите 2 (Range Maximum Query с обновлением узла)
- Итеративное дерево сегментов (запрос максимального диапазона с обновлением узла)
- Сегментное дерево | Набор 1 (сумма заданного диапазона)
- Сегментное дерево | Набор 3 (XOR заданного диапазона)
- Сегментное дерево | (XOR заданного диапазона)
- Запросы для элементов больше K в заданном диапазоне индекса с использованием дерева сегментов
- Минимальный запрос диапазона (разложение по квадратным корням и разреженная таблица)
- Обзор структур данных | Набор 3 (График, Три, Сегментное дерево и Суффикс-дерево)
- Декартово дерево из обхода обхода | Сегментное дерево
- Два запроса диапазона сегментов с одинаковой суммой
- Запрос диапазона для подсчета установленных бит
- Запрос диапазона значений с использованием Sparse Table
- Сегмент деревьев | (Продукт заданного диапазона по модулю м)
- Разница Массив | Запрос на обновление диапазона в O (1)
0.00 (0%) 0 votes