Изменения

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

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

1 байт добавлено, 00:16, 15 апреля 2012
Разреженная таблица
Простой метод построения таблицы заключён в следующем реккурентном соотношении:
 
<tex> ST[i][j] =
\left\{
\begin{array}{lclrcl}
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j > 0 \\
A[i], j = 0 \\
Анонимный участник

Навигация