Введение

Сегодня мне хотелось бы рассказать о методе эффективного вычисления суммы элементов массива с l-того по r-тый. Самый известный из таких методов — это древо отрезков(RSQ), но он довольно сложен в написании и понимании, поэтому я хочу предложить более простой, но менее эффективный — Sqrt-декомпозиция.

Формальная постановка задачи

Дан массив A[0..n-1], нам нужно научиться эффективно вычислять сумму элементов A[l..r] для произвольных l и r, не выходящих за пределы массива. Без ограничения общности будем считать, что l <= r.