Sparse table — различия между версиями
| Строка 8: | Строка 8: | ||
'''''Идея решения'''''<br> | '''''Идея решения'''''<br> | ||
Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n), k e [0, log n]. Таким образом, у нас O(n lon n) чисел. <br> | Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n), k e [0, log n]. Таким образом, у нас O(n lon n) чисел. <br> | ||
| − | + | ''Шаг 0.'' <br> | |
При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br> | При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br> | ||
...<br> | ...<br> | ||
| − | + | ''Шаг k.'' <br> | |
Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) U [I + 2^(k-1), i + 2^k). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).<br> | Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) U [I + 2^(k-1), i + 2^k). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).<br> | ||
В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована. | В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована. | ||
Версия 19:21, 4 апреля 2020
Задача RMQ.
Формулировка проблемы.
Есть массив, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами от L до R (не включая R)".
Идея решения
Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n), k e [0, log n]. Таким образом, у нас O(n lon n) чисел.
Шаг 0.
При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив.
...
Шаг k.
Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) U [I + 2^(k-1), i + 2^k). Минимумы на этих полуинтервалах мы считали на предыдущем шаге. (vis 7:45). Таким образом, каждое такое значение мы посчитаем за O(1).
В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.
