Бюрократы, editor, Администраторы
422
правки
Изменения
Первая половина — описание алгоритма, подготавливающего почву. Пока без картинок.
'''Алгоритм Фарака-Колтона, Бендера (алгоритм Фарах-Колтона, Бендера)''' — алгоритм решения специального случая задачи RMQ (поиска минимума на отрезке), в котором соседние элементы входной последовательности различаются на ±1. Может быть использован также для [[Сведение задачи LCA к задаче RMQ|решения задачи LCA]].
'''Вход:''' последовательность <tex>a_i</tex> длины <tex>N</tex>.<br/>
'''Выход:''' ответы на онлайн запросы вида «минимум на отрезке <tex>[i:j]</tex>».
== На пути к успеху ==
Начнём с рассмотрения алгоритма общей задачи RMQ, требующего <tex>O(log N)</tex> времени на предварительную обработку данных и <tex>O(1)</tex> времени для ответа на каждый запрос.
Основная идея заключается в том, чтобы предподсчитать ответы для отрезков, длины которых являются степенями двойки. То есть <tex>M_i^k = min\{a_i, .., a_{i+2^k}\}</tex> — минимум на отрезке длины <tex>2^k</tex>, начинающемся в позиции <tex>i</tex>. Таким образом, таблица <tex>M</tex> имеет размер <tex>O(N logN)</tex>. Заполнить эту таблицу можно за <tex>O(N logN)</tex>, если заметить, что <tex>M_i^0 = a_i</tex> и <tex>M_i^k = min\{M_i^{k-1}, M_{i+2^{k-1}}^{k-1}\}</tex> ''(см. картинку)''.
Пусть теперь необходимо вычислить минимум на отрезке <tex>[i:j]</tex>. Для этого мы покроем этот отрезок двумя отрезками длины <tex>2^k</tex> (где <tex>k = \lfloor log_2(j-i) \rfloor</tex>) так, чтобы первый отрезок начинался в <tex>i</tex>, а второй заканчивался в <tex>j - 1</tex>. Отрезки, разумеется, будут пересекаться, то это никак не помешает. В этом случае искомый минимум можно найти за константное время как минимум на этих двух блоках, т.е. <tex>min([i:j]) = min\{M_i^k, M_{j-2^k}^k\}</tex>.
== Ссылки ==
* M. A. Bender and M. Farach-Colton. "The LCA Problem Revisited" LATIN, pages 88-94, 2000
'''Вход:''' последовательность <tex>a_i</tex> длины <tex>N</tex>.<br/>
'''Выход:''' ответы на онлайн запросы вида «минимум на отрезке <tex>[i:j]</tex>».
== На пути к успеху ==
Начнём с рассмотрения алгоритма общей задачи RMQ, требующего <tex>O(log N)</tex> времени на предварительную обработку данных и <tex>O(1)</tex> времени для ответа на каждый запрос.
Основная идея заключается в том, чтобы предподсчитать ответы для отрезков, длины которых являются степенями двойки. То есть <tex>M_i^k = min\{a_i, .., a_{i+2^k}\}</tex> — минимум на отрезке длины <tex>2^k</tex>, начинающемся в позиции <tex>i</tex>. Таким образом, таблица <tex>M</tex> имеет размер <tex>O(N logN)</tex>. Заполнить эту таблицу можно за <tex>O(N logN)</tex>, если заметить, что <tex>M_i^0 = a_i</tex> и <tex>M_i^k = min\{M_i^{k-1}, M_{i+2^{k-1}}^{k-1}\}</tex> ''(см. картинку)''.
Пусть теперь необходимо вычислить минимум на отрезке <tex>[i:j]</tex>. Для этого мы покроем этот отрезок двумя отрезками длины <tex>2^k</tex> (где <tex>k = \lfloor log_2(j-i) \rfloor</tex>) так, чтобы первый отрезок начинался в <tex>i</tex>, а второй заканчивался в <tex>j - 1</tex>. Отрезки, разумеется, будут пересекаться, то это никак не помешает. В этом случае искомый минимум можно найти за константное время как минимум на этих двух блоках, т.е. <tex>min([i:j]) = min\{M_i^k, M_{j-2^k}^k\}</tex>.
== Ссылки ==
* M. A. Bender and M. Farach-Colton. "The LCA Problem Revisited" LATIN, pages 88-94, 2000
