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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

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

На новой последовательности [math]B_i[/math] построим разреженную таблицу. При этом размер разреженной таблицы и время её построения будут равны:

[math]\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}[/math] [math]+2N=O(N)[/math]

Теперь для ответа на запрос [math]\mathrm{RMQ}[/math][math][l:r][/math], если [math]l[/math] и [math]r[/math] находятся в разных блоках, нам необходимо вычислить следующее:

• минимум на отрезке от [math]l[/math] до конца блока, содержащего [math]l[/math];
• минимум по всем блокам, находящимся между блоками, содержащими [math]l[/math] и [math]r[/math];
• минимум от начала блока, содержащего [math]r[/math], до [math]r[/math].

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

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

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

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

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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Псевдокод

 function precalc(A: int[N]): 
   block_size = log(N) / 2  // размеры блоков 
   K = [math]\lceil[/math]N / block_size[math]\rceil[/math]  // количество блоков  
   // предподсчитаем позиции минимумов в каждом блоке
   cur_block = -1
   for i = 0 to K - 1 
     B[i] = -1 
   for i = 0 to N - 1
     if i mod block_size == 0 
       cur_block++ 
     if B[cur_block] = -1 or A[B[cur_block]] > A[i]
       B[cur_block] = i
   // построим Sparse table на массиве B
   for i = 0 to K - 1
     ST[i][0] = B[i]
   for j = 1 to log(N)
     for i = 0 to K - 1
       ind = (1 << (j - 1)) + i
       if ind ≥ K
         ST[i][j] = ST[i][j - 1]
       else if A[ST[i][j - 1]] > A[ST[ind][j - 1]]
         ST[i][j] = ST[ind][j - 1] 
       else
         ST[i][j] = ST[i][j - 1]
   // Посчитаем тип для каждого блока
   for i = 0 to K - 1 
     type[i] = 0 
   cur_block = 0
   j = 0
   i = 0
   while i < N or j < block_size
     if j ≥ block_size 
       j = 0
       cur_block++ 
     if j > 0 and (i ≥ N or A[i - 1] < A[i])
       type[cur_block] += (1 << (j - 1)) 
     i++
     j++
   // Осталось только для каждого блока предподсчитать позиции минимумов на всех подотрезках
   for i = 0 to K - 1
     for l = 0 to block_size - 1
       for r = 0 to block_size - 1
         block_min[i][l][r] = -1 
   for i = 0 to K - 1
     t = type[i]
     if block_min[t][0][0] = -1 // если там записано, что-то отличное от -1, то значит, мы уже посчитали ответ для такого типа отрезков
       for l = 0 to block_size - 1
         block_min[t][l][l] = l
         for r = l + 1 to block_size - 1
           block_min[t][l][r] = block_min[t][l][r - 1]
           if i * block_size + r ≤ N and A[i * block_size + block_min[t][l][r]] > A[i * block_size + r]
               block_min[t][l][r] = r

 function block_RMQ(block_number: int, l: int, r: int): int
   return block_min[type[block_number]][l][r] + block_number * block_size

 function RMQ(l: int, r: int): int
   bl = l / block_size
   br = r / block_size
   if bl = br // если оба индекса внутри одного блока
     return A[block_RMQ(bl, l % block_size, r % block_size)]
   if bl + 1 < br // найдем минимум на блоках между крайними, если таковые есть
     power = log(br - bl - 1)
     ansb = min(A[ST[bl + 1][power]], A[ST[br - (1 << power)][power]])
   ansl = A[block_RMQ(bl, l % block_size, block_size - 1)] // найдем минимум на отрезке от l до конца блока, содержащего l
   ansr = A[block_RMQ(br, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r    
   return min(ansb, min(ansl, ansr))

Результат

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