Алгоритм Фарака-Колтона и Бендера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Текст, кажется, готов)
(Добавлена картинка)
Строка 5: Строка 5:
  
 
== Алгоритм ==
 
== Алгоритм ==
 +
[[Файл:F-C_B_algo.png|right|thumb|Части, из которых состоит ответ на запрос RMQ]]
 +
 
Данный алгоритм основывается на методе решения задачи RMQ с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex><O(N \log N),O(1)></tex>.
 
Данный алгоритм основывается на методе решения задачи RMQ с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex><O(N \log N),O(1)></tex>.
  
 
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>a_i</tex> на блоки длины <tex>\frac{\log_2 N}{2}</tex>. Для каждого блока вычислим минимум на нём и определим <tex>b_i</tex> как позицию минимального элемента в <tex>i</tex>-том блоке.
 
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>a_i</tex> на блоки длины <tex>\frac{\log_2 N}{2}</tex>. Для каждого блока вычислим минимум на нём и определим <tex>b_i</tex> как позицию минимального элемента в <tex>i</tex>-том блоке.
  
На новой последовательности <tex>b_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос RMQ<tex>[i:j]</tex> нам необходимо вычислить следующее:
+
На новой последовательности <tex>b_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос RMQ<tex>[i:j]</tex>, если <tex>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
 
# Минимум на отрезке от <tex>i</tex> до конца содержащего <tex>i</tex> блока.
 
# Минимум на отрезке от <tex>i</tex> до конца содержащего <tex>i</tex> блока.
 
# Минимум по всем блокам, находящимся между блоками, содержащими <tex>i</tex> и <tex>j</tex>.
 
# Минимум по всем блокам, находящимся между блоками, содержащими <tex>i</tex> и <tex>j</tex>.
Строка 16: Строка 18:
  
 
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>b_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.
 
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>b_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.
 +
 +
=== Минимум внутри блока ===
  
 
{{Утверждение
 
{{Утверждение

Версия 22:40, 9 мая 2011

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

Вход: последовательность [math]a_i[/math] длины [math]N[/math].
Выход: ответы на онлайн запросы вида «минимум на отрезке [math][i:j][/math]».

Алгоритм

Части, из которых состоит ответ на запрос RMQ

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

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

На новой последовательности [math]b_i[/math] построим разреженную таблицу. Теперь для ответа на запрос RMQ[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]b_i[/math] и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.

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

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

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

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

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

Результат

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

См. также

Ссылки

  • M. A. Bender and M. Farach-Colton. “The LCA Problem Revisited” LATIN, pages 88-94, 2000