Изменения

Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex> было выбрано равным <tex>\lfloor \sqrt{n} \rfloor</tex>, и а <tex>cnt</tex> выбирано было выбрано равным <tex>~ ~ \approx left\sqrtlceil \dfrac{n}{len} \right\rceil</tex>, то для выполнения операции на отрезке <tex>[l, r]</tex> понадобится <tex>O(\sqrt{n})</tex> времени.