Sparse table — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
Строка 7: Строка 7:
  
 
'''''Идея решения'''''<br>
 
'''''Идея решения'''''<br>
Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n), k e [0, log n]. Таким образом, у нас O(n lon n) чисел.  
+
Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n), k e [0, log n]. Таким образом, у нас O(n lon n) чисел. <br>
 
Шаг 0. <br>
 
Шаг 0. <br>
 
При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br>
 
При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br>

Версия 19:20, 4 апреля 2020

Задача RMQ.


Формулировка проблемы.
Есть массив, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами от L до R (не включая R)".

Идея решения
Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n), k e [0, log n]. Таким образом, у нас O(n lon n) чисел.
Шаг 0.
При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив.
...
Шаг k.
Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) U [I + 2^(k-1), i + 2^k). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).
В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.