Изменения

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

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

11 байт добавлено, 13:45, 3 марта 2016
Нет описания правки
'''Алгоритм Фарака-Колтона, Бендера''' (англ. ''Farach-Colton, Bender'') — применяется для решения за <tex>\langle O(N),O(1) \rangle</tex> времени специального случая задачи <tex>RMQ</tex> (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на <tex>±1</tex>. Может быть использован также для [[Сведение задачи LCA к задаче RMQ|решения задачи <tex>LCA</tex>]].
{{Задача
Анонимный участник

Навигация