Викиконспекты - Вклад участника [ru]

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

2018-05-11T08:19:05Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
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 < K
'''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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

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

2018-05-10T09:48:42Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
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 < K
'''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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

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

2018-05-10T09:42:55Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
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 < K
'''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 <tex>\leqslant </tex> 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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

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

2018-05-10T09:41:33Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
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 < K
'''if''' j <tex>\geqslant</tex> 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 <tex>\leqslant </tex> 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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

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

2018-05-10T09:34:19Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
cur_block = -1
j = 0
'''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 <tex>\ge</tex> 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 < K
'''if''' j <tex>\geqslant</tex> block_size
j = 0
cur_block++
'''if''' j > 0 '''and''' (i <tex>\geqslant</tex> 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 <tex>\leqslant </tex> 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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

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

2018-05-10T09:31:33Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
cur_block = 0
j = 0
'''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 <tex>\geq</tex> 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 < K
'''if''' j <tex>\geqslant</tex> block_size
j = 0
cur_block++
'''if''' j > 0 '''and''' (i <tex>\geqslant</tex> 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 <tex>\leqslant </tex> 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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

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

2018-05-10T09:27:23Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
cur_block = 0
j = 0
'''for''' i = 0 '''to''' K - 1
B[i] = -1
'''for''' i = 0 '''to''' N - 1
'''if''' j <tex>\ge</tex> block_size
j = 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 <tex>\geq</tex> 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 < K
'''if''' j <tex>\geqslant</tex> block_size
j = 0
cur_block++
'''if''' j > 0 '''and''' (i <tex>\geqslant</tex> 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 <tex>\leqslant </tex> 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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

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

2018-05-10T09:22:50Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
cur_block = 0
j = 0
'''for''' i = 0 '''to''' K - 1
B[i] = -1
'''for''' i = 0 '''to''' N - 1
'''if''' j <tex>\geq</tex> block_size
j = 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 <tex>\geq</tex> 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 < K
'''if''' j <tex>\geqslant</tex> block_size
j = 0
cur_block++
'''if''' j > 0 '''and''' (i <tex>\geqslant</tex> 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 <tex>\leqslant </tex> 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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

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

2018-05-10T09:22:18Z

217.197.4.113: /* Псевдокод */

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

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

== Алгоритм ==

Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.

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

=== Псевдокод ===
<code>

'''function''' precalc(A: '''int[N]'''):
block_size = log(N) / 2 // размеры блоков 
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> // количество блоков 
// предподсчитаем позиции минимумов в каждом блоке
cur_block = 0
j = 0
'''for''' i = 0 '''to''' K - 1
B[i] = -1
'''for''' i = 0 '''to''' N - 1
'''if''' j <tex>\geqslant</tex> block_size
j = 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 <tex>\geq</tex> 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 < K
'''if''' j <tex>\geqslant</tex> block_size
j = 0
cur_block++
'''if''' j > 0 '''and''' (i <tex>\geqslant</tex> 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 <tex>\leqslant </tex> 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 // найдем минимум на блоках между крайними, если таковые есть
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(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r 
'''return''' min(ansb, min(ansl, ansr))

</code>

=== Результат ===
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.

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

==Источники информации==
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]