Изменения

<tex>\sum_{i = l}^r a_i = \sum_{i = l}^{(k + 1)len - 1} + a_i \sum_{i = k}^p b_i + \sum_{i = p + 1}^r a_i</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 - декомпозиция]