Sqrt-декомпозиция — это метод, или структура данных, позволяющая в режиме онлайн проводить такие операции, как подсчет суммы на отрезке за 
и обновление элемента за 
. Существуют более эффективные структуры, такие как дерево фенвика или дерево отрезков, которые оба запроса обрабатывают за 
. Однако я хочу рассказать про корневую оптимизацию, т.к. в этом методе заложена идея, применимая к задачам другого типа.
<img src="https://www.pvsm.ru/images/1f981e5234e325a6ed00a4287833c833.png"/>
Постановка задачи
Пусть нам задан массив A[i], на который поступают запросы вида:
- посчитать сумму на отрезке [L; R] (позже, мы поймем, что аналогично можно вычислять функции min, max, gcd и др.
- добавить к элементу A[i], delta
Наивная реализация
Мы можем предрасчитать массив частичных сумм, а именно:
for(int j = 0; j < i; j++) B[j] += A[i];и тогда на запрос суммы [L; R], мы будем возвращать B[R]-B[L-1] за . Однако на запрос изменения, потребует пересчета частичных сумм (содержащих этот элемент) и в худшем случае составит асимптотику порядка 
, что не есть хорошо.
Построение декомпозиции
Основной идеей будет то, что 
* = 
. А именно, если у нас есть элементов, то всех их мы можем разбить на блоков, где каждый длиной , кроме, может быть, последнего. Затем для всех блоков мы посчитаем сумму чисел на нем, сразу можно увидеть, что вспомогательный массив будет занимать памяти.
Опишем построение массива sqrtSums[]:
int len = (int)sqrt(n) + 1; //длина каждого "sqrt-отрезка" int sqrtSums[MAXN], st = 0; //массив предпросчитанных сумм for(int i = 0; i < n; i++) sqrtSums[i / len] += A[i]; Описание запросов
Запрос суммы (RSQ)
Рассмотрим запрос суммы [L; R], для «быстрого» ответа на него, необходимо максимально использовать уже имеющуюся информацию. Как мы уже говорили, Sum[L; R] = Sum[0, R] — Sum[0; L-1]. Осталось научиться обрабатывать запрос Sum[0; R]. Заметим, что несколько первых отрезков ([0; len-1], [len; 2*len-1], ...) будут полностью входить в запрос [0; R], а значит мы можем использовать информацию из sqrtSums[] (за , так как отрезков всего ). Однако у нас останется «хвостик» вида: [k*len; k*len + delta] (delta < len, т.к. иначе, мы сможем включить еще один отрезок [k*len; (k+1)*len-1]), его мы сможем посчитать вручную (delta < len, на асимптотику, , не повлияет). Приведем пример реализации:
int getPartSum(int r) { int it = 0, res = 0; while((it+1) * len -1 <= r) res += sqrtSums[it++]; //прибавляем предпосчитанные отрезки, пока можем for(int i = it*len; i <=r; i++) res += A[i]; //прибавляем "хвост" return res; } int getSum(int l, int r) { if(l == 0) return getPartSum(r); else return getPartSum(r) - getPartSum(l-1); }
Запрос на изменение элемента
Во многих структурах, для реализации данного запроса, требуется опуститься по дереву, или посчитать хеш-функцию, или еще что-то… Однако тут нам необходимо поменять всего 2 значения (каждый элемент входит в ровно один «sqrt-отрезок»)
int incElement(int index, int delta) { A[index] += delta; sqrtSums[index/len] += delta; } Range Min/Max/Gcd Query
Чтобы отвечать на запросы RMQ(Range Min / Max Query) нужно почти тоже самое, что и для сумм. Однако стоит отметить, чтобы обновить элемент «в тупую», нам потребуется времени (при обновлении элемента, пересчитывать min/max на всем «sqrt-отрезке»), но если наложить на обновления некоторые ограничения, то мы добьемся оценки . А именно, при решении задачи поиска минимума/максимума, разрешать только уменьшать/увеличивать элемент.
Код для обновления минимума:
int decElement(int index, unsigned int delta) //delta - на сколько уменьшить элемент { A[index] -= delta; sqrtSums[index/len] = min(sqrtSums[index/len], A[index]); } Аналогично для обновления максимума:
int incElement(int index, unsigned int delta) //delta - на сколько увеличить элемент { A[index] += delta; sqrtSums[index/len] = max(sqrtSums[index/len], A[index]); } Нужно добавить, что в задаче RMQ, задача не сводится к [0; R] — [0; L-1], т.е. придется вычислять минимум/максимум с L по R (не считая заново, полностью входящие в [L; R] «sqrt-отрезки», подумайте, почему асимптотика не поменяется, а чистое время работы может даже улучшится...).
Для вычисления GCD (Greatest Common Divisor), мы не сможем использовать ту «фишку», что мы провернули для min/max. Поэтому обе операции вычисляются за .
Код для GCD (для минимума и максимума функции getGCD заменятся на min/max):
int getGCD(int a, int b) { while(a && b) { if(a < b) b %= a; else a %= b; } return a + b; } int gcdRQ(int l, int r) { int cur_gcd = A[l++]; for(int i = l; i <= r;) if (i % len == 0 && i + len - 1 <= r) { cur_gcd = getGCD(cur_gcd, b[i / len]); i += len; //перескок через "sqrt-отрезок" } else cur_gcd = getGCD(cur_gcd, A[i++]); } Источники
Пользовался этим сайтом, а именно.
Так как вдохновила на статью лекция из Харьковской Зимней Компьютерной Школы, то кину сайт, возможно скоро там появится сборник за этот год, с видео-лекциями.
Пока все, надеюсь, что было понятно.
Автор: antonchig
