Изменения

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

'''Вход:''' последовательность {{Задача|definition = Дан массив <tex>a_iA[1 \ldots N]</tex> длины целых чисел, соседние элементы которого отличаются на <tex>N\pm 1</tex>.Поступают онлайн запросы вида <tex>(l, r)<br/tex>'''Выход:''' ответы на онлайн запросы вида «минимум на отрезке , для каждого из которых требуется найти минимум среди элементов <tex>A[l], A[l + 1], \ldots, A[i:jr]</tex>».}}

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

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

Пусть теперь необходимо вычислить минимум на отрезке Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>[i:j]A_i</tex>. Для этого мы покроем этот отрезок двумя отрезками на блоки длины <tex>K=\dfrac{1}{2^k</tex> (где <tex>k = }\lfloor log_2(j-i) \rfloorN</tex>) так, чтобы первый отрезок начинался в . Для каждого блока вычислим минимум на нём и определим <tex>iB_i</tex>, а второй заканчивался как позицию минимального элемента в <tex>j - 1i</tex>. Отрезки, разумеется, будут пересекаться, то это никак не помешает. В этом случае искомый минимум можно найти за константное время как минимум на этих двух блоках, т.е. <tex>min([i:j]) = min\{M_i^k, M_{j-2^k}^k\}</tex>ом блоке.

 На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. При этом размер разреженной таблицы и время её построения будут равны: <tex>\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}</tex> <tex>+2N=O(N)</tex> Теперь для ответа на запрос <tex>\mathrm{RMQ}</tex><tex>[l:r]</tex>, если <tex>l</tex> и <tex>r</tex> находятся в разных блоках, нам необходимо вычислить следующее: * минимум на отрезке от <tex>l</tex> до конца блока, содержащего <tex>l</tex>;* минимум по всем блокам, находящимся между блоками, содержащими <tex>l</tex> и <tex>r</tex>;* минимум от начала блока, содержащего <tex>r</tex>, до <tex>r</tex>.Ответом на запрос будет позиция меньшего из этих трёх элементов. [[Файл:F-C_B_algo.png|500px|center|Части, из которых состоит ответ на запрос RMQ]] Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>B_i</tex> и разреженной таблицы. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков. === Минимум внутри блока === {{Утверждение|id=sameblocks|statement=Если две последовательности <tex>x_i</tex> и <tex>y_i</tex> таковы, что все их элементы на соответствующих позициях различаются на одну и ту же константу (т.е. <tex>\forall k: x_k = y_k + C</tex>), то любой запрос <tex>\mathrm{RMQ}</tex> даст один и тот же ответ для обеих последовательностей.}} Таким образом, мы можем ''нормализовать'' блок, вычтя из всех его элементов первый. Тем самым мы значительно уменьшим число возможных типов блоков. {{Утверждение|id=kindscount|statement=Существует <tex>O(\sqrt N)</tex> различных типов нормализованных блоков.|proof=Соседние элементы в блоках отличаются на <tex>\pm 1</tex>. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен <tex>\pm 1</tex>-вектором длины <tex> \bigg(\dfrac{1}{2} \log_2 N\bigg) - 1</tex>. Таких векторов <tex>2^{(\frac{1}{2} \log_2 N) - 1} = O(\sqrt N)</tex>.}} Осталось создать <tex>O(\sqrt N)</tex> таблиц {{---}} по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, которых <tex>\bigg(\dfrac{1}{2}\log_2 N\bigg)^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>B_i</tex> необходимо заранее вычислить его тип. Для этого нужно подобрать некоторую функцию из множества блоков в множество натуральных чисел, не вызывающую коллизий. Например, вектор из нулей и единиц, соответствующий типу блока, можно записать в целочисленный тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(N)</tex> времени. === Псевдокод ===  '''function''' precalc(A: '''int[N]'''): block_size = log(N) / 2 <font color=green> // размеры блоков </font> K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> <font color=green> // количество блоков </font> <font color=green>// предподсчитаем позиции минимумов в каждом блоке</font> 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 <font color=green>// построим Sparse table на массиве B</font> '''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 &ge; 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] <font color=green>// Посчитаем тип для каждого блока</font> '''for''' i = 0 '''to''' K - 1 type[i] = 0 cur_block = 0 j = 0 i = 0 '''while''' i < N or j < K '''if''' j &ge; block_size j = 0 cur_block++ '''if''' j > 0 '''and''' (i &ge; N '''or''' A[i - 1] < A[i]) type[cur_block] += (1 << (j - 1)) i++ j++ <font color=green>// Осталось только для каждого блока предподсчитать позиции минимумов на всех подотрезках</font> '''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 <font color=green>// если там записано, что-то отличное от -1, то значит, мы уже посчитали ответ для такого типа отрезков</font> '''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 * Mblock_size + r &le; 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 <font color=green>// если оба индекса внутри одного блока</font> '''return''' A[block_RMQ(bl, l % block_size, r % block_size)] '''if''' bl + 1 < br <font color=green>// найдем минимум на блоках между крайними, если таковые есть</font> 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)] <font color=green>// найдем минимум на отрезке от l до конца блока, содержащего l</font> ansr = A[block_RMQ(bl, 0, r % block_size)] <font color=green>// найдем минимум от начала блока, содержащего r, до r </font> '''return''' min(ansb, min(ansl, ansr)) === Результат ===Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>. A == См. также ==* [[Решение RMQ с помощью разреженной таблицы]]* [[Сведение задачи RMQ к задаче LCA]]* [[Сведение задачи LCA к задаче RMQ]] ==Источники информации==* Bender and , M. A., Farach-Colton, M. "{{---}} The LCA Problem Revisited" . LATIN(2000), pages с. 88-94, 2000 [[Категория: Алгоритмы и структуры данных]][[Категория: Задача о наименьшем общем предке]]