Найти минимальный элемент подпоследовательности

Question

задана последовательностью S из n целочисленных элементов, мне нужна функция min(i,j), которая находит минимальный элемент последовательности между индексом г и индексом J (оба включительно) таким образом, что:

1. Инициализация занимает O(n);
2. Площадь памяти O(n);
3. min(i,j) принимает O(log(n)).

Просьба предложить алгоритм для этого.

Answer 1

Segmenttree - это то, что вам нужно, потому что оно отвечает всем вашим требованиям.

1. Инициализация занимает O (п) с Segment Tree
2. памяти также O (п)
3. Запросы можно сделать в O (Log п)

Кроме этого, дерево динамический и может поддерживать обновление в O (log n). Это означает, что можно изменить элемент некоторого элемента i в O (log n) и по-прежнему получить минимум.

Answer 2

Этот учебник TopCoder: An < O(n), O(1) > approach обсуждает вашу проблему более подробно. В обозначениях означает, что для подхода требуется сложность f (n) и сложность запроса (g).

Кроме того, этот пост снова повторяет алгоритм: Range Minimum Query <O(n), O(1)> approach (from tree to restricted RMQ).

Надежда их проясняют ваш вопрос :)

Answer 3

Сегмент дерева является только то, что вам нужно (это может быть построено в O(n) времени и один запрос занимает O(log n) время). Вот статья об этом: http://wcipeg.com/wiki/Segment_tree.
Хотя алгоритм использует O(n) время для инициализации и O(1) времени на запрос, дерево сегментов может быть хорошим выбором, потому что это намного проще.