Минимальный запрос псевдодальности

Question

У меня есть проблема с моим назначением, которая требует от меня решения проблемы, аналогичной диапазону минимального запроса. Проблема примерно описана ниже:

Я должен кодировать Java-программу, которая читает большое количество целых чисел (около 100 000) и сохраняет их в некоторой структуре данных. Затем моя программа должна отвечать на запросы для минимального числа в данном диапазоне [i,j]. Я успешно разработал алгоритм для решения этой проблемы. Тем не менее, это просто не достаточно быстро.

Псевдокод для моего алгоритма выглядит следующим образом:

// Read all the integers into an ArrayList

// For each query,
// Read in range values [i,j] (note that i and j is "actual index" + 1 in this case)
// Push element at index i-1 into a Stack
// Loop from index i to j-1 in the ArrayList (tracking the current index with variable k)
[Begin loop]       
// If element at k is lesser than the one at the top of the stack, push the element at k into the Stack.
[End of loop]

Может ли кто-нибудь сообщить мне, что я могу сделать, чтобы мой алгоритм был достаточно быстрым, чтобы решить эту проблему?

Файлы с заданиями можно найти по этой ссылке: http://bit.ly/1bTfFKa

Я был озадачен этой проблемой в течение нескольких дней. Любая помощь приветствуется. Благодарю.

Answer 1

Ваша проблема - запрос минимального статического диапазона (RMQ). Предположим, у вас есть N номеров. Самым простым алгоритмом, который вы можете использовать, является алгоритм, который будет создавать массив размера N и хранить числа, а другой - размер sqrtN и будет содержать RMQ каждого интервала размера sqrtN в массиве. Это должно работать, так как N не очень велико, но если у вас много запросов, вы можете использовать другой алгоритм.
При этом самый быстрый алгоритм, который вы можете использовать, - это составление разреженной таблицы из чисел, которая позволит вам отвечать на запросы в O(1). Построение разреженной таблицы - это O(NlogN), что, учитывая N = 10^5, должно быть в порядке.
Наконец, в конечном алгоритме RMQ используется дерево сегментов, которое также поддерживает обновления (одноэлементные, а также диапазоны), и его O(N) для построения дерева сегментов и O(logN) для каждого запроса и обновления. Все эти алгоритмы очень хорошо представлены здесь. Для получения дополнительной информации в Деревьях сегмента посмотрите эти учебники, которые я написал сам. ссылка на сайт
Удачи!