Sparse table

Задача 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) обоснована.

Как нам это поможет решить заявленную задачу? Рассмотрим вновь поступивший запрос GetMin (L, R). Вместим в него слева и справа по полуинтервалу максимальной длины из тех, на которых мы считали минимумы на предыдущем шаге (разумеется, их длины окажутся равны) (viz 10:20). Докажем, что при таком покрытии покрывающие полуинтервалы обязательно пересекутся. Действительно, пусть это не так. Но тогда каждый из полуинтервалов занимает меньше половины [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 мы не можем отвечать на такие запросы в случае, когда массив меняется, поскольку не придуман эффективный по времени алгоритм обновления минимумов на подотрезках.