Корневая декомпозиция.

Необходимость

Иногда запросы на отрезках (и не только - круг применения техники куда шире) невозможно решить деревом отрезков никак. Тогда на помощь приходит корневая декомпозиция (sqrt-декомпозиция).

Особенность заключается в том, что мы можем все-таки перебрать некоторые элементы в лоб, пересчитать что-то и т.п.

Идея

Основная идея декомпозиции заключается в том, что если разбить \(n\) элементов на блоки по \(\sqrt{n}\) элементов, то всего блоков тоже будет \(\sqrt{n}\).

Таким образом, мы можем делать за одну итерацию:

любые \(O(1)\) операции над всеми \(\sqrt{n}\) блоками

любые \(O(\sqrt{n})\) операции над \(O(1)\) блоками.

Асимптотика тогда не будет превышать \(O(q\sqrt{n})\), где \(q\) - количество итераций.

Сумма на отрезке

Простейшая задача - сумма на отрезке \([l;r]\) без запросов изменений.

Первый блок - первые \(\sqrt{n}\) элементов массива, второй - следующие и т.п. \(i\)-й элемент принадлежит \( \lfloor \frac{i}{\sqrt{n}}\rfloor\)-му блоку. Предподсчитаем сумму каждого блока.

Когда приходит запрос - смотрим на все блоки что целиком входят в границы отрезка запроса и суммируем их. Далее проверяем все элменты что не вошли в блоки. Это какой-то суффикс \( \lfloor \frac{l}{\sqrt{n}} \rfloor \)-го блока и префикс \( \lfloor \frac{r}{\sqrt{n}} \rfloor \)-го. Их можно перебрать, так как суммарно их меньше чем \(2\sqrt{n}\).

Итого: \(O(\sqrt{n})\) на запрос. Легко решается и задача, с обновлением в точке: просто пересчитать один блок.

int a[n];
int C = sqrt(n); //размер блока
int blocks[n/C+1];//сумма блоков

for(int i = 0; i < n; i++)
 blocks[i/C]+=a[i];

//ответ на запрос:
int l,r; // границы отрезка

int sum=0;

if(l/C==r/C) //отдельно обработываем этот случай
 for(int i = l;i <= r; i++)
  sum+=a[i];
else
 {
  // считаем те блоки, что полностью внутри запроса
  for(int i = 1+l/C; i < r/C; i++)
   sum+=blocks[i];
  // считаем сумму хвостов:
  for(int i = l; i/C==l/C; i++)
   sum+=a[i];
  for(int j = (r/C)*C; i <= r; i++)
   sum+=a[i];
 }
// sum - ответ

Вообще размер блока \(\sqrt{n}\) - асимптотически лучший вариант. Но часто используют размер блока, как какую-то степень двойки, так как дорогостоящее деление будет происходить быстрее.

Прибавление на отрезке.

Допустим у нас добавился запрос прибавления на отрезке.

Когда будет приходить такой запрос, мы на самом деле честно прибавим только для "хвостов" (обновляя сумму блока), а для остальных блоков мы запишем для каждого блока в \(lazy\), что мы прибавили им какое-то значение.

Во время вычисления суммы на отрезке необходимо учитывать факт того, что к некоторым блокам мы прибавляли, то есть, кроме \(blocks[i]\), к ответу прибавим еще \(lazy[i]*C\).