Улучшение производительности RMQ движущегося окна

Question

Улучшение производительности RMQ движущегося окна

Скажем, у меня есть массив целых A длины Nтакже у меня есть целое число L <знак равно N,

То, что я пытаюсь найти, — это минимум диапазона [0, L-1], [1, L], [2, L + 1] …. [N-L, N-1]

(как движущееся окно длины L слева направо)

Мой алгоритм теперь O (N lg N) с O (N lg N) препроцессом:

Сохранить все номера A[0...L-1] в множестве Sтакже храните номер в очереди Q с целью. Минимум [0, L-1] является просто первым элементом S, O (N lg N)
Выскочить первый элемент Qнайти этот элемент в S и удали его. Затем нажмите A[L] в S, Минимум [1, L] является просто первым элементом S, O (LG N)
Повторите шаг 2 для всех возможных диапазонов, переходите к следующему элементу каждую итерацию. НА)

Всего O (N lg N).

Интересно, есть ли какой-нибудь алгоритм, который может добиться большего, чем этот, при следующих требованиях:

Время предварительной обработки (при необходимости) составляет O (N)
Время запроса, если O (1)

Я провел некоторое исследование RMQ, ближайший метод, который я нашел, использует разреженную таблицу, которая достигает O (1) времени запроса, но O (N lg N) времени предварительной обработки. Еще один метод, который уменьшить RMQ до LCA проблема может соответствовать требованиям, но она нуждается в ограничении массива A,

Так возможно ли, что без ограничений на Aтребования могут быть выполнены при решении моей проблемы?

1

algorithm c++rmq

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Да, использовать Deque. Мы будем хранить элементы отсортированными по возрастанию, поэтому первый элемент всегда минимальный в [i - L + 1, i], для текущей позиции i, Мы не будем сохранять фактические элементы, но их позиции.

d = empty deque
for i = 0 to n-1:

// get rid of too old elements
while !d.empty && i - d.front + 1 > L:
d.pop_front()

// keep the deque sorted
while !d.empty && A[d.back] > A[i]
d.pop_back()

d.push_back(i)
// A[d.front] is the minimum in `[i - L + 1, i]

Поскольку каждый элемент входит и покидает деку не более одного раза, это O(n),

2