Алгоритм Фарака-Колтона и Бендера

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

Вход: последовательность [math]a_i[/math] длины [math]N[/math].
Выход: ответы на онлайн запросы вида «минимум на отрезке [math][i:j][/math]».

На пути к успеху

Построение таблицы [math]M_i^k[/math]

Начнём с рассмотрения алгоритма решения общей задачи RMQ, требующего [math]O(log N)[/math] времени на предварительную обработку данных и [math]O(1)[/math] времени для ответа на каждый запрос.

Основная идея заключается в том, чтобы предподсчитать ответы для отрезков, длины которых являются степенями двойки. То есть [math]M_i^k = min\{a_i, .., a_{i+2^k}\}[/math] — минимум на отрезке длины [math]2^k[/math], начинающемся в позиции [math]i[/math]. Таким образом, таблица [math]M[/math] имеет размер [math]O(N logN)[/math]. Заполнить эту таблицу можно за [math]O(N logN)[/math] динамически, если заметить, что [math]M_i^0 = a_i[/math] и [math]M_i^k = min\{M_i^{k-1}, M_{i+2^{k-1}}^{k-1}\}[/math] (см. картинку).

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

Ссылки

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