Обсуждение участника:Shovkoplyas Grigory

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

Задача:

Дан массив [math]A[1 \ldots N][/math] целых чисел, соседние элементы которой отличаются на [math]\pm 1[/math]. Поступают онлайн запросы вида [math](l, r)[/math], для каждого из которых требуется найти минимум среди элементов [math]A[l], A[l + 1], \ldots, A[r] [/math].

Алгоритм

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

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

Псевдокод

int interpolationSearch(a : int[], key : int)  // a должен быть отсортирован 
  left = 0  // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) 
  right = a.length - 1  // правая граница поиска 

  while a[left] < key and key < a[right]
    mid = left + (key - a[left]) * (right - left) / (a[right] - a[left])  // индекс элемента, с которым будем проводить сравнение 
    if a[mid] < key
      left = mid + 1
    else if a[mid] > key
      right = mid - 1
    else
      return mid

  if a[left] == key
    return left
  else if a[right] == key
    return right
  else
    return -1 // если такого элемента в массиве нет 

На новой последовательности [math]B_i[/math] построим разреженную таблицу. Теперь для ответа на запрос [math]RMQ[/math][math][i:j][/math], если [math]i[/math] и [math]j[/math] находятся в разных блоках, нам необходимо вычислить следующее:

1. минимум на отрезке от [math]i[/math] до конца блока, содержащего [math]i[/math];
2. минимум по всем блокам, находящимся между блоками, содержащими [math]i[/math] и [math]j[/math];
3. минимум от начала блока, содержащего [math]j[/math], до [math]j[/math].

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

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

Минимум внутри блока

Утверждение:

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

Таким образом, мы можем нормализовать блок, вычтя из всех его элементов первый. Тем самым мы значительно уменьшим число возможных типов блоков.

Утверждение:

Существует [math]O(\sqrt N)[/math] различных типов нормализованных блоков.

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Осталось создать [math]O(\sqrt N)[/math] таблиц — по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, которых [math](\frac{1}{2}\log_2 N)^2 = O(\log^2 N)[/math]. Для каждого блока в [math]B_i[/math] необходимо заранее вычислить его тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за [math]O(1)[/math], затратив на предподсчёт [math]O(\sqrt N \log^2 N)[/math] времени.

Результат

Итого, на предподсчёт требуется [math]O(N)[/math] времени и памяти, а ответ на запрос вычисляется за [math]O(1)[/math].

См. также

• Решение RMQ с помощью разреженной таблицы
• Сведение задачи RMQ к задаче LCA
• Сведение задачи LCA к задаче RMQ

Источники информации

• Bender, M.A., Farach-Colton, M. — The LCA Problem Revisited. LATIN (2000), с. 88-94