Бюрократы, editor, Администраторы
422
правки
Изменения
Добавлена картинка
== Алгоритм ==
[[Файл:F-C_B_algo.png|right|thumb|Части, из которых состоит ответ на запрос RMQ]]
Данный алгоритм основывается на методе решения задачи RMQ с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex><O(N \log N),O(1)></tex>.
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>a_i</tex> на блоки длины <tex>\frac{\log_2 N}{2}</tex>. Для каждого блока вычислим минимум на нём и определим <tex>b_i</tex> как позицию минимального элемента в <tex>i</tex>-том блоке.
На новой последовательности <tex>b_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос RMQ<tex>[i:j]</tex> , если <tex>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
# Минимум на отрезке от <tex>i</tex> до конца содержащего <tex>i</tex> блока.
# Минимум по всем блокам, находящимся между блоками, содержащими <tex>i</tex> и <tex>j</tex>.
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>b_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.
=== Минимум внутри блока ===
{{Утверждение
