Изменения

Размер каждого из "хвостов", очевидно, не превосходит длины блока <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> операцийвремени.