Изменения

'''Алгоритм Фарака-Колтона, Бендера (алгоритм Фарах-Колтона, Бендера)''' — применяется для решения за <tex>\langle O(N),O(1) \rangle</tex> времени специального случая задачи RMQ (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на ±1. Может быть использован также для [[Сведение задачи LCA к задаче RMQ|решения задачи LCA]].

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи RMQ с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

# минимум от начала блока, содержащего <tex>j</tex>, до <tex>j</tex>.

Ответом на запрос будет позиция меньшего из эти трёх элементов.

Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>b_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.