Изменения

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

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

54 байта добавлено, 20:18, 31 марта 2012
Применение к задаче 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][k], ST[r-2^k+1][j]\right)</tex>. Заметим <tex>k</tex> зависит лишь от длины отрезка. Предпосчитать эту величину за <tex>O(N\log N)</tex> можно следующим образом: введением функции <tex>fl[l] = k</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>. Теперь мы можем находить <tex>k</tex> за <tex>O(1)</tex>. Таким образом, ответ на запрос происходит за константное время.</div>
<div style="clear:both"></div>
355
правок

Навигация