Изменения

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

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

Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>A_i</tex> на блоки длины <tex>K=\fracdfrac{1}{2}\log_2 N</tex>. Для каждого блока вычислим минимум на нём и определим <tex>B_i</tex> как позицию минимального элемента в <tex>i</tex>-ом блоке.

На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. При этом размер разреженной таблицы и время её построения будут равны: <tex>\dfrac{N}{K}\log\dfrac{N}{K}=\bigg(\dfrac{2N}{\log N}\bigg)\log\bigg(\dfrac{2N}{\log N}\bigg)=\bigg(\dfrac{2N}{\log N}\bigg)\bigg(1+\log\bigg(\dfrac{N}{\log N}\bigg)\bigg)\leqslant \dfrac{2N}{\log N}</tex> <tex>+2N=O(N)</tex> Теперь для ответа на запрос <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>.Ответом на запрос будет позиция меньшего из эти этих трёх элементов.

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

|statement=Если две последовательности <tex>x_i</tex> и <tex>y_i</tex> таковы, что все их элементы на соответствующих позициях различаются на одну и ту же константу (т.е. <tex>\forall k: x_k = y_k + C</tex>), то любой запрос <tex>\mathrm{RMQ}</tex> даст один и тот же ответ для обеих последовательностей.

|proof=Соседние элементы в блоках отличаются на <tex>\pm 1</tex>. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен <tex>\pm 1</tex>-вектором длины <tex> \bigg(\fracdfrac{1}{2} \log_2 N\bigg) - 1</tex>. Таких векторов <tex>2^{(\frac{1}{2} \log_2 N) - 1} = O(\sqrt N)</tex>.

Осталось создать <tex>O(\sqrt N)</tex> таблиц {{---}} по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, которых <tex>\bigg(\fracdfrac{1}{2}\log_2 N\bigg)^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>B_i</tex> необходимо заранее вычислить его тип. Для этого нужно подобрать некоторую функцию из множества блоков в множество натуральных чисел, не вызывающую коллизий. Например, вектор из нулей и единиц, соответствующий типу блока, можно записать в целочисленный тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(\sqrt N \log^2 N)</tex> времени. 

precalc(A : '''int[]function''', N precalc(A: '''int[N]''') :

cur_block = 0 j = 0 -1

'''if''' j <tex>\ge</tex> i '''mod''' block_size j == 0

'''if''' ind <tex>\&ge</tex> ; K

<font color=green>// Посчитаем хеш тип для каждого блока {{---}} он будет являться типом блока</font> '''for''' i = 0 '''to''' K - 1 type[i] = 0

'''for''' i = 0 '''to''' K - 1 hash[i] = 0 '''forwhile''' i = 0 '''to''' < N - 1or j < K '''if''' j <tex>\&ge</tex> ; block_size

'''if''' j > 0 '''and''' (i <tex>\&ge</tex> n ; N '''or''' A[i - 1] < A[i]) hashtype[cur_block] += (1 << (j - 1)) i++ j++

t = type = hash[i] '''if''' block_min[typet][0][0] = -1 <font color=green>// если там записано, что-то отличное от -1, то значит, мы уже посчитали ответ для такого типа отрезков</font>

block_min[typet][l][l] = l

block_min[typet][l][r] = block_min[typet][l][r - 1] '''if''' i * block_size + r <tex>\&le</tex> ; N '''and''' A[i * block_size + block_min[typet][l][r]] > A[i * block_size + r] block_min[typet][l][r] = r

'''intfunction''' block_RMQ(block_number : '''int''', l : '''int''', r : '''int'''): '''int''' '''return''' block_min[hashtype[block_number]][l][r] + block_number * block_size

'''intfunction''' RMQ(l : '''int''', r : '''int'''): '''int'''

power = log(br - bl + - 1)