Алгоритмы / [Из песочницы] Sqrt-декомпозиция (корневая оптимизация)

в 12:56, , рубрики: структуры данных, метки:

Sqrt-декомпозиция — это метод, или структура данных, позволяющая в режиме онлайн проводить такие операции, как подсчет суммы на отрезке за image и обновление элемента за image. Существуют более эффективные структуры, такие как дерево фенвика или дерево отрезков, которые оба запроса обрабатывают за image. Однако я хочу рассказать про корневую оптимизацию, т.к. в этом методе заложена идея, применимая к задачам другого типа.

<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] за image. Однако на запрос изменения, потребует пересчета частичных сумм (содержащих этот элемент) и в худшем случае составит асимптотику порядка image, что не есть хорошо.

Построение декомпозиции

Основной идеей будет то, что image * image = image. А именно, если у нас есть image элементов, то всех их мы можем разбить на image блоков, где каждый длиной image, кроме, может быть, последнего. Затем для всех блоков мы посчитаем сумму чисел на нем, сразу можно увидеть, что вспомогательный массив будет занимать image памяти.
Опишем построение массива 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[] (за image, так как отрезков всего image). Однако у нас останется «хвостик» вида: [k*len; k*len + delta] (delta < len, т.к. иначе, мы сможем включить еще один отрезок [k*len; (k+1)*len-1]), его мы сможем посчитать вручную (delta < len, на асимптотику, image, не повлияет). Приведем пример реализации:

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) нужно почти тоже самое, что и для сумм. Однако стоит отметить, чтобы обновить элемент «в тупую», нам потребуется image времени (при обновлении элемента, пересчитывать min/max на всем «sqrt-отрезке»), но если наложить на обновления некоторые ограничения, то мы добьемся оценки image. А именно, при решении задачи поиска минимума/максимума, разрешать только уменьшать/увеличивать элемент.
Код для обновления минимума:

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. Поэтому обе операции вычисляются за image.
Код для 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

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js