Изменения

Перейти к: навигация, поиск

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

6 байт убрано, 19:45, 9 мая 2011
м
Нет описания правки
Начнём с рассмотрения '''алгоритма решения общей задачи 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

Навигация