Search
Write a publication
Pull to refresh

Sqrt-декомпозиция

Reading time2 min
Views3K
Введение

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

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

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


Решение

Воспользуемся методом Sqrt-декомпозиции. Данный метод позволяет решать поставленную задачу за . Суть метода заключается в том что мы делим исходный массив на блоки длины и производим некий предподсчёт. Очевидно, что таких блоков получится штук. Последний блок может быть короче других, если n не делится нацело на , но в этом нет ничего страшного.

Пусть длина блока 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, где лежит изменяемый элемент. На это, очевидно, нужно операций. Так же данный метод можно применять для вычисления минимума и максимума на отрезке массива. Для этого нужно в В хранить минимумы и максимумы соответствующих блоков.
Tags:
Hubs:
Total votes 40: ↑28 and ↓12+16
Comments12

Articles