Sparse table — различия между версиями
(→Как нам это поможет решить заявленную задачу?) |
|||
| (не показано 18 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | + | == Задача RMQ. == | |
| − | |||
'''''Формулировка проблемы.'''''<br> | '''''Формулировка проблемы.'''''<br> | ||
| − | Есть массив, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами | + | Есть массив из n элементов, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами из полунтервала [L, R)". <br> |
| − | + | == Идея решения == | |
| − | Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i | + | Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i ∈ [0, n), k ∈ [0, log n]. Таким образом, у нас O(n log n) чисел. <br> |
| − | Шаг 0. <br> | + | ''Шаг 0.'' <br> |
При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br> | При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив. <br> | ||
...<br> | ...<br> | ||
| − | Шаг k. <br> | + | ''Шаг k.'' <br> |
| − | Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) | + | Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге (иллюстрация ниже). Таким образом, каждое такое значение мы посчитаем за O(1).<br> |
В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована. | В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована. | ||
| + | [[Файл:vis1.png]] | ||
| + | |||
| + | == Как нам это поможет решить заявленную задачу? == | ||
| + | Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [L, R]. Тогда их можно увеличить в два раза так, что они по прежнему будут внутри [L, R]. Таким образом, получено противоречие с выбором максимальности вписанных полуинтервалов. <br>Но раз эти отрезки пересекаются и мы знаем минимум на каждом из них, предпочитав его, мы можем ответить на запрос за O(1) при условии быстрого нахождения нужных полуинтервалов для вписывания. <br> | ||
| + | [[Файл:vis2.png]]<br> | ||
| + | Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для R - L = 1 нам нужна нулевая степень (a[1] = 0), для R - L = 2 - первая (a[2] = 1), ... а для R - L = n соответствующая степень a[n] = a[n/2] + 1. Весь этот цикл выполняется за O(n) - это мелочи по сравнению с тем, сколько мы потратили на предподсчеты минимумов. <br> | ||
| + | Таким образом, оценка доказана. <br><br> | ||
| + | '''''Проблема'''''<br> | ||
| + | С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках. | ||
Текущая версия на 12:34, 15 мая 2020
Задача RMQ.
Формулировка проблемы.
Есть массив из n элементов, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами из полунтервала [L, R)".
Идея решения
Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i ∈ [0, n), k ∈ [0, log n]. Таким образом, у нас O(n log n) чисел.
Шаг 0.
При k = 0 все, что нужно сделать, это пройтись один раз по массиву, сохранив его, поскольку это просто полуинтервалы вида [i, i + 1), то есть ровно наш изначально заданный массив.
...
Шаг k.
Заметим, что [i, i + 2^k) = [i, i + 2^(k-1)) ∪ [i + 2^(k-1), i + 2^(k-1)). Минимумы на этих полуинтервалах мы считали на предыдущем шаге (иллюстрация ниже). Таким образом, каждое такое значение мы посчитаем за O(1).
В сухом остатке, мы провели O(log n) шагов ценой O(n) каждый - оценка O(n log n) обоснована.
Как нам это поможет решить заявленную задачу?
Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [L, R]. Тогда их можно увеличить в два раза так, что они по прежнему будут внутри [L, R]. Таким образом, получено противоречие с выбором максимальности вписанных полуинтервалов.
Но раз эти отрезки пересекаются и мы знаем минимум на каждом из них, предпочитав его, мы можем ответить на запрос за O(1) при условии быстрого нахождения нужных полуинтервалов для вписывания.
Мы можем предподсчитать нужную степень двойки для каждой длины отрезка из запроса. Для этого воспользуемся тем, что для R - L = 1 нам нужна нулевая степень (a[1] = 0), для R - L = 2 - первая (a[2] = 1), ... а для R - L = n соответствующая степень a[n] = a[n/2] + 1. Весь этот цикл выполняется за O(n) - это мелочи по сравнению с тем, сколько мы потратили на предподсчеты минимумов.
Таким образом, оценка доказана.
Проблема
С помощью sparse table мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.
