Изменения
→Обработка запроса
Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) {{---}} не полностью.
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.
[[Файл:sqrt(sum).png|358px]]
Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex>, и <tex>cnt</tex> мы выбирали <tex>~ ~ \approx \sqrt{n}</tex>, то для выполнения операции на отрезке <tex>[l, r]</tex> нам понадобится <tex>O(\sqrt{n})</tex> времени.
== Запрос на изменение элемента ==
