Изменения

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

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

Нет изменений в размере, 22:33, 5 сентября 2019
м
Правка орфографии
Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \leqslant N </tex>.
Простой метод построения таблицы заключён в следующем реккурентном рекуррентном соотношении:
$$
ST[i][j]=
24
правки

Навигация