Изменения

Перейти к: навигация, поиск

Алгоритм Фарака-Колтона и Бендера

Нет изменений в размере, 14:03, 3 марта 2016
Алгоритм
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос <tex>\mathrm{RMQ}</tex><tex>[l:r]</tex>, если <tex>l</tex> и <tex>r</tex> находятся в разных блоках, нам необходимо вычислить следующее:
# * минимум на отрезке от <tex>l</tex> до конца блока, содержащего <tex>l</tex>;# * минимум по всем блокам, находящимся между блоками, содержащими <tex>l</tex> и <tex>r</tex>;# * минимум от начала блока, содержащего <tex>r</tex>, до <tex>r</tex>.
Ответом на запрос будет позиция меньшего из эти трёх элементов.
Анонимный участник

Навигация