Изменения
→Обработка запроса
== Обработка запроса ==
Пусть мы получили получен запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) {{---}} не полностью.
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.
Размер каждого из "хвостов", очевидно, не превосходит длины блока <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> времени.
== Запрос на изменение элемента ==
