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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Несколько уточнений)
м
Строка 9: Строка 9:
 
Начнём с рассмотрения '''алгоритма решения общей задачи RMQ''', требующего <tex>O(log N)</tex> времени на предварительную обработку данных и <tex>O(1)</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>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>.
+
Пусть теперь необходимо вычислить минимум на отрезке <tex>[i:j]</tex>. Для этого мы покроем этот отрезок двумя отрезками длины <tex>2^k</tex> (где <tex>k = \lfloor log_2(j-i) \rfloor</tex>) так, чтобы первый отрезок начинался в <tex>i</tex>, а второй заканчивался в <tex>j</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
 
* M. A. Bender and M. Farach-Colton. "The LCA Problem Revisited" LATIN, pages 88-94, 2000

Версия 19:45, 9 мая 2011

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

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

На пути к успеху

Построение таблицы [math]M_i^k[/math]

Начнём с рассмотрения алгоритма решения общей задачи RMQ, требующего [math]O(log N)[/math] времени на предварительную обработку данных и [math]O(1)[/math] времени для ответа на каждый запрос.

Основная идея заключается в том, чтобы предподсчитать ответы для отрезков, длины которых являются степенями двойки. То есть [math]M_i^k = min\{a_i, .., a_{i+2^k}\}[/math] — минимум на отрезке длины [math]2^k[/math], начинающемся в позиции [math]i[/math]. Таким образом, таблица [math]M[/math] имеет размер [math]O(N logN)[/math]. Заполнить эту таблицу можно за [math]O(N logN)[/math] динамически, если заметить, что [math]M_i^0 = a_i[/math] и [math]M_i^k = min\{M_i^{k-1}, M_{i+2^{k-1}}^{k-1}\}[/math] (см. картинку).

Пусть теперь необходимо вычислить минимум на отрезке [math][i:j][/math]. Для этого мы покроем этот отрезок двумя отрезками длины [math]2^k[/math] (где [math]k = \lfloor log_2(j-i) \rfloor[/math]) так, чтобы первый отрезок начинался в [math]i[/math], а второй заканчивался в [math]j[/math]. Отрезки, разумеется, будут пересекаться, то это никак не помешает. В этом случае искомый минимум можно найти за константное время как минимум на этих двух покрывающих отрезках, т.е. [math]min([i:j]) = min\{M_i^k, M_{j-2^k}^k\}[/math].


Ссылки

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