Найти минимум в диапазоне i-j меньше, чем в O (j-i), используя меньше, чем O (N ^ 2) памяти
Скажем, есть большой массив, который содержит N целых чисел:
const unsigned N = 1e12;
int array[N] = { 1, 3 , 8, -5, 4, 3, -1 -6, 6, ....., N};
Там должен быть запрошен много раз наименьший элемент в диапазоне различных i j indecies. Сложность возврата минимума должна быть меньше, чем в O (J-I), и проблема должна быть решена с использованием меньше, чем O (N ^ 2) памяти.
Как это можно сделать?
Решение
Для статического массива, как вы упомянули, самым быстрым решением является O (1) с O (n) preproc. Но на практике вы можете использовать один из следующих подходов, которые также работают для динамических массивов и кажутся мне более простыми для понимания и кодирования:
- разделите массив на секции sqrt (n), каждая с элементами sqrt (n), и сохраните минимумы для каждого из этих сегментов. Каждый (i, j) будет полностью содержать некоторые из этих сегментов плюс, возможно, некоторые элементы слева и справа. Передайте эти элементы и сохраненные ответы для сегментов, чтобы найти мин. Это требует O (n) preproc, O (sqrt (n)) запроса, O (sqrt (n)) обновления и O (sqrt (n)) памяти. Также очень легко кодировать.
- построить дерево минимальных сегментов над массивом. Это дает O (logn) для запроса / обновления, O (n) памяти / preproc.
Другие решения
RMQ работает следующим образом:
Мы сохраняем массив M [N] [logN], где M [i] [j] показывает минимальное количество диапазонов, начиная с i и имея длину 2 ^ j. Чтобы заполнить этот массив, сначала мы вычисляем все значения M [i] [0], которые все равны M [i] [0] = A [i] (A [i] — исходный массив). После этого по индукции каждый M [i] [j] будет равен мин (M [i] [j — 1], M [i + (1 << (j — 1))] [j — 1]) то есть мы получаем значения для более длинных интервалов, беря минимум его левого & правильные части, которые должны быть рассчитаны на предыдущем шаге, поскольку мы движемся от самых коротких до самых длинных интервалов.
После этого, чтобы получить минимальное значение в интервале [a..b], вам нужно найти наибольшее P, такое, что 2 ^ P не превышает длину интервала [a..b]. И ответ будет мин (M [a] [P], M [b — (1 << P) + 1] [P])
Для тех, кто знает русский язык это решение: http://e-maxx.ru/algo/rmq
Для тех, кто не знает русского языка, извините, я не нашел что-то. Если кто-то найдет, отредактируйте мой ответ.
Простое решение — создать двумерный массив, в котором запись [i, j] хранит минимальное значение в диапазоне arr [i..j]. Минимум заданного диапазона теперь можно вычислить за время O (1), но предварительная обработка занимает время O (n ^ 2). Кроме того, этот подход требует O (n ^ 2) дополнительного пространства, которое может стать огромным для больших входных массивов.
Другое решение состоит в том, чтобы построить дерево сегментов. Дерево сегментов можно использовать для предварительной обработки и выполнения запросов за умеренное время. Для дерева сегментов время предварительной обработки равно O (n), а время для минимального диапазона запроса равно O (Logn). Требуется дополнительное пространство O (n) для хранения дерева сегментов.
Представление Сегментных деревьев
- Конечные узлы являются элементами входного массива.
- Каждый внутренний узел представляет минимум всех листьев под ним.
Построение дерева сегментов подробно объясняется здесь:
http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/