Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
'''Алгоритм Фарака-Колтона, Бендера (алгоритм Фарах-Колтона, Бендера)''' — применяется для решения специального случая задачи RMQ (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на ±1 за <tex>\langle O(N),O(1) \rangle</tex> времениспециального случая задачи RMQ (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на ±1. Может быть использован также для [[Сведение задачи LCA к задаче RMQ|решения задачи LCA]].
'''Вход:''' последовательность <tex>a_i</tex> длины <tex>N</tex>, соседние элементы которой отличаются на ±1.<br/>
'''Выход:''' ответы на онлайн запросы вида «минимум «позиция минимума на отрезке <tex>[i:j]</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>j</tex>, до <tex>j</tex>.
Ответом на запрос будет позиция меньшего из эти трёх элементов.
|id=kindscount
|statement=Существует <tex>O(\sqrt N)</tex> различных типов нормализованных блоков.
|proof=Соседние элементы в блоках отичаются отличаются на ±1. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен ±1-вектором длины <tex>(\frac{\log_2 N}{2}) - 1</tex>. Таких векторов <tex>2^{(1/2 \cdot \log_2 N) - 1} = O(\sqrt N)</tex>.
}}
