148
правок
Изменения
Нет описания правки
Теперь разрешим изменять элементы. Если меняется какой-то элемент <tex>a_i</tex>, то достаточно пересчитать значение <tex>b_k</tex> в том блоке, в котором этот элемент находится:
<tex>b_k\ = \min(new_value, a_j)</tex>, где <tex>a_j</tex> - элементы блока <tex>b_k</tex>
<tex>(k = i / len)</tex>
==Оценка сложности==
Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex>, и <tex>cnt</tex> мы выбирали <tex>\approx \sqrt{n}</tex>, то всего для вычисления суммы в минимума и пересчитывания на отрезке <tex>[l \ldots r]</tex> нам понадобится <tex>O(\sqrt{n})</tex> операций.
==Источники==
[http://www.e-maxx.ru/algo/sqrt_decomposition Maximal:: algo:: Sqrt - декомпозиция]
