Бюрократы, editor, Администраторы
422
правки
Изменения
м
Нет описания правки
[[Файл:Sparse_table.png|right|thumb|Построение таблицы <tex>M_i^k</tex>]]
Начнём с рассмотрения '''алгоритма решения общей задачи RMQ''', требующего <tex>O(log N)</tex> времени на предварительную обработку данных и <tex>O(1)</tex> времени для ответа на каждый запрос.
Основная идея заключается в том, чтобы предподсчитать ответы для отрезков, длины которых являются степенями двойки. То есть <tex>M_i^k = min\{a_i, .., a_{i+2^k}\}</tex> — минимум на отрезке длины <tex>2^k</tex>, начинающемся в позиции <tex>i</tex>. Таким образом, таблица <tex>M</tex> имеет размер <tex>O(N logN)</tex>. Заполнить эту таблицу можно за <tex>O(N logN)</tex>, если заметить, что <tex>M_i^0 = a_i</tex> и <tex>M_i^k = min\{M_i^{k-1}, M_{i+2^{k-1}}^{k-1}\}</tex> ''(см. картинку)''.
