Обсуждение участника: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]-ом блоке.

На новой последовательности [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] времени.

Псевдокод

 precalc(A : int[], N : int) 
   block_size = log(N) / 2  // размеры блоков 
   K = [math]\lceil[/math]N / block_size[math]\rceil[/math]  // количество блоков  
   // предподсчитаем позиции минимумов в каждом блоке
   cur_block = 1 
   for i = 1 to K 
     B[i] = -1 
   for i = 1 to N 
     if j > block_size 
       j = 1
       cur++ 
     if B[cur] = -1 or A[B[cur]] > A[i]
       B[cur] = i

Результат

Итого, на предподсчёт требуется [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