Введение
Сегодня мне хотелось бы рассказать о методе эффективного вычисления суммы элементов массива с l-того по r-тый. Самый известный из таких методов — это древо отрезков(RSQ), но он довольно сложен в написании и понимании, поэтому я хочу предложить более простой, но менее эффективный — Sqrt-декомпозиция.
Формальная постановка задачи
Дан массив A[0..n-1], нам нужно научиться эффективно вычислять сумму элементов A[l..r] для произвольных l и r, не выходящих за пределы массива. Без ограничения общности будем считать, что l <= r.
Решение
Воспользуемся методом Sqrt-декомпозиции. Данный метод позволяет решать поставленную задачу за




Пусть длина блока len =


А если n на len нацело не делится, то длина последнего блока будет не len, а меньше. Что, как было сказано ранее, не принципиально.
Далее создадим массив B, в B[i] будем хранить сумму элементов i-го блока. Очевидно, что такой предподсчёт займёт

Поэтому при запросе суммы нам не нужно пробегать по всем элементам массива с l по r, так как у нас уже подсчитаны частичные суммы. Рассмотрим пример.
Пусть A = {3, 4, 8, 7, 1, 6, 1, 6 }, тогда len = 3, B[0] = 15, B[1] = 14, B[2] = 7.
А спрашивают у нас сумму элементов с 1-го по 6-ой (нумеруем с нуля).

Сначала нам придётся честно пробежаться по двум элементам массива и сложить 4 и 8, так как нам нужна не полная сумма B[0], а только часть. Далее нам не надо бежать по массиву, так как B[1] уже посчитано и равно 14, ну и наконец добавить 1, тоже как бы пробежавшись, так как нужна не полная сумма последнего блока.
Реализация:
//У нас есть массив A (заданный) и B — массив частичных сумм.
//len — длина блока
for (int i = 0; i < n; i++)
B[i / len] += A[i]; //Вычисляем сумму блоков
//l и r — границы
int i = l, sum = 0;
while(i <= r)
{
if(i % len == 0 && i + len -1 <= r)
{
sum += B[i / len];
i += len;
}
else
{
sum += A[i];
i++;
}
}
В sum и будет находиться результат.
Ещё одним плюсом данного метода является то, что мы можем очень просто изменять элементы массива. При изменении элемента массива A нам всего лишь нужно пересчитать тот элемент из B, где лежит изменяемый элемент. На это, очевидно, нужно
