Изменения

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

== На пути к успеху Алгоритм ==Данный алгоритм основывается на методе решения задачи RMQ с помощью [[Файл:Sparse_table.png|right|thumbРешение RMQ с помощью разреженной таблицы|Построение разреженной таблицы (sparse table, ST)]] за <tex>M_i^k<O(N \log N),O(1)></tex>]].

Начнём с рассмотрения '''алгоритма решения общей задачи RMQ''', требующего Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>a_i</tex> на блоки длины <tex>O(log \frac{\log_2 N)}{2}</tex> времени . Для каждого блока вычислим минимум на предварительную обработку данных нём и определим <tex>b_i</tex> как позицию минимального элемента в <tex>O(1)i</tex> времени для ответа на каждый запрос-том блоке.

Основная идея заключается в том, чтобы предподсчитать ответы для отрезков, длины которых являются степенями двойки. То есть На новой последовательности <tex>M_i^k = min\{a_i, .., a_{i+2^k}\}b_i</tex> — минимум построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на отрезке длины запрос RMQ<tex>2^k[i:j]</tex>, начинающемся в позиции нам необходимо вычислить следующее:# Минимум на отрезке от <tex>i</tex>. Таким образом, таблица до конца содержащего <tex>Mi</tex> имеет размер блока.# Минимум по всем блокам, находящимся между блоками, содержащими <tex>O(N logN)i</tex>. Заполнить эту таблицу можно за и <tex>O(N logN)j</tex> динамически, если заметить.# Минимум от начала блока, что содержащего <tex>M_i^0 = a_ij</tex> и , до <tex>M_i^k = min\{M_i^{k-1}, M_{i+2^{k-1}}^{k-1}\}j</tex> ''(см. картинку)''Ответом на запрос будет позиция меньшего из эти трёх элементов.

Пусть теперь необходимо вычислить минимум на отрезке <tex>[i:j]</tex>. Для этого Второй элемент мы покроем этот отрезок двумя отрезками длины <tex>2^k</tex> (где уже умеем находить за <tex>k = \lfloor log_2O(j-i) \rfloor</tex>1) так, чтобы первый отрезок начинался в <tex>i</tex>, а второй заканчивался в с помощью <tex>jb_i</tex>и ST. Отрезки, разумеется, будут пересекатьсяОсталось научиться находить минимум по отрезку, то это никак границы которого не помешает. В этом случае искомый минимум можно найти за константное время как минимум на этих двух покрывающих отрезках, т.е. <tex>min([i:j]) = min\{M_i^k, M_{j-2^k}^k\}</tex>совпадают с границами блоков.

* M. A. Bender and M. Farach-Colton. "The “The LCA Problem Revisited" Revisited” LATIN, pages 88-94, 2000