69
правок
Изменения
Новая страница: «'''Алгоритм Фарака-Колтона, Бендера (алгоритм Фарах-Колтона, Бендера)''' — применяется для ...»
'''Алгоритм Фарака-Колтона, Бендера (алгоритм Фарах-Колтона, Бендера)''' — применяется для решения за <tex>\langle O(N),O(1) \rangle</tex> времени специального случая задачи RMQ (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на ±1. Может быть использован также для [[Сведение задачи LCA к задаче RMQ|решения задачи LCA]].
'''Вход:''' последовательность <tex>a_i</tex> длины <tex>N</tex>, соседние элементы которой отличаются на ±1.<br/>
'''Выход:''' ответы на онлайн запросы вида «позиция минимума на отрезке <tex>[i:j]</tex>».
== Алгоритм ==
[[Файл:F-C_B_algo.png|right|thumb|Части, из которых состоит ответ на запрос RMQ]]
Данный алгоритм основывается на методе решения задачи RMQ с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex>\langle O(N \log N),O(1) \rangle</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>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
# минимум на отрезке от <tex>i</tex> до конца содержащего <tex>i</tex> блока;
# минимум по всем блокам, находящимся между блоками, содержащими <tex>i</tex> и <tex>j</tex>;
# минимум от начала блока, содержащего <tex>j</tex>, до <tex>j</tex>.
Ответом на запрос будет позиция меньшего из эти трёх элементов.
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>b_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.
=== Минимум внутри блока ===
{{Утверждение
|id=sameblocks
|statement=Если две последовательности <tex>x_i</tex> и <tex>y_i</tex> таковы, что все их элементы на соответствующих позициях различаются на одну и ту же константу (т.е. <tex>\forall k: x_k = y_k + C</tex>), то любой запрос RMQ даст один и тот же ответ для обеих последовательностей.
}}
Таким образом, мы можем ''нормализовать'' блок, вычтя из всех его элементов первый. Тем самым мы значительно уменьшим число возможных типов блоков.
{{Утверждение
|id=kindscount
|statement=Существует <tex>O(\sqrt N)</tex> различных типов нормализованных блоков.
|proof=Соседние элементы в блоках отличаются на ±1. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен ±1-вектором длины <tex>(\frac{\log_2 N}{2}) - 1</tex>. Таких векторов <tex>2^{(1/2 \cdot \log_2 N) - 1} = O(\sqrt N)</tex>.
}}
Осталось создать <tex>O(\sqrt N)</tex> таблиц — по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, коих <tex>(\frac{\log_2 N}{2})^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>b_i</tex> необходимо заранее вычислить его тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(\sqrt N \log^2 N)</tex> времени.
=== Результат ===
Итого, на предподсчёт требуется <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
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]
'''Вход:''' последовательность <tex>a_i</tex> длины <tex>N</tex>, соседние элементы которой отличаются на ±1.<br/>
'''Выход:''' ответы на онлайн запросы вида «позиция минимума на отрезке <tex>[i:j]</tex>».
== Алгоритм ==
[[Файл:F-C_B_algo.png|right|thumb|Части, из которых состоит ответ на запрос RMQ]]
Данный алгоритм основывается на методе решения задачи RMQ с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex>\langle O(N \log N),O(1) \rangle</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>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
# минимум на отрезке от <tex>i</tex> до конца содержащего <tex>i</tex> блока;
# минимум по всем блокам, находящимся между блоками, содержащими <tex>i</tex> и <tex>j</tex>;
# минимум от начала блока, содержащего <tex>j</tex>, до <tex>j</tex>.
Ответом на запрос будет позиция меньшего из эти трёх элементов.
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>b_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.
=== Минимум внутри блока ===
{{Утверждение
|id=sameblocks
|statement=Если две последовательности <tex>x_i</tex> и <tex>y_i</tex> таковы, что все их элементы на соответствующих позициях различаются на одну и ту же константу (т.е. <tex>\forall k: x_k = y_k + C</tex>), то любой запрос RMQ даст один и тот же ответ для обеих последовательностей.
}}
Таким образом, мы можем ''нормализовать'' блок, вычтя из всех его элементов первый. Тем самым мы значительно уменьшим число возможных типов блоков.
{{Утверждение
|id=kindscount
|statement=Существует <tex>O(\sqrt N)</tex> различных типов нормализованных блоков.
|proof=Соседние элементы в блоках отличаются на ±1. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен ±1-вектором длины <tex>(\frac{\log_2 N}{2}) - 1</tex>. Таких векторов <tex>2^{(1/2 \cdot \log_2 N) - 1} = O(\sqrt N)</tex>.
}}
Осталось создать <tex>O(\sqrt N)</tex> таблиц — по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, коих <tex>(\frac{\log_2 N}{2})^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>b_i</tex> необходимо заранее вычислить его тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(\sqrt N \log^2 N)</tex> времени.
=== Результат ===
Итого, на предподсчёт требуется <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
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]
