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