Изменения

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

Решение RMQ с помощью разреженной таблицы

150 байт добавлено, 00:25, 26 марта 2012
Применение к задаче RMQ
== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
<div>Дан запрос <tex>(l, r)</tex>. По нему найдём <tex>k = \max \{j: | 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка.Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l, j][k], ST[r-2^jk+1,][j]\right)</tex>. Таким образом, если находить Заметим <tex>jk</tex> зависит лишь от длины отрезка. Предпосчитаем эту величину за <tex>O(N\log N)</tex> следующим образом: <tex>fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1)</tex> (например, предподсчётом . Теперь мы можем находить <tex>k</tex> за <tex>O(N \log N1)</tex> для всех возможных длин отрезков). Таким образом, можно отвечать ответ на запрос происходит за константное время.</div>
<div style="clear:both"></div>
 
== Источники ==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.
355
правок

Навигация