Sqrt decomposition (root optimization)

Sqrt decomposition is a method, or data structure, that allows you to perform operations online such as calculating the amount in a segment for and updating an element for . There are more efficient structures, such as the Fenwick tree or the tree of segments , which both requests process for . However, I want to talk about root optimization, because this method has an idea that is applicable to tasks of a different type.

Formulation of the problem

Let us be given an array A [i], to which requests of the form:

• calculate the amount on the segment [L; R] (later, we will understand that the functions min, max, gcd, etc. can be calculated similarly.
• add to element A [i], delta

Naive implementation

We can calculate an array of partial amounts, namely:

 for(int j = 0; j < i; j++) B[j] += A[i];

and then at the request of the amount [L; R], we will return B [R] -B [L-1] for . However, upon requesting a change, it will require recounting of partial sums (containing this element) and, in the worst case, will make an asymptotic order , which is not good.

Decomposition

The main idea will be that * = . Namely, if we have elements, then we can divide all of them into blocks, where each is long , except maybe the last one. Then, for all blocks, we calculate the sum of the numbers on it, you can immediately see that the auxiliary array will occupy memory.
We describe the construction of the sqrtSums [] array:

int len = (int)sqrt(n) + 1; //длина каждого "sqrt-отрезка"
int sqrtSums[MAXN], st = 0; //массив предпросчитанных сумм
for(int i = 0; i < n; i++)
	sqrtSums[i / len] += A[i];

Request Description

Amount Request (RSQ)

Consider a query for the sum [L; R], for a “quick” answer to it, it is necessary to use the information already available to the maximum. As we have said, Sum [L; R] = Sum [0, R] - Sum [0; L-1]. It remains to learn how to process the request Sum [0; R]. Note that the first few segments ([0; len-1], [len; 2*len-1], ...)will be fully included in the request [0; R], which means we can use information from sqrtSums[](behind , since there are segments of everything ). However, we will have a “tail” of the form: [k*len; k*len + delta](delta <len, because otherwise, we can include another segment [k*len; (k+1)*len-1]), we can calculate it manually (delta <len , it will not affect the asymptotic behavior ). Here is an example implementation:

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); 
}

Item Change Request

In many structures, to implement this query, you need to go down the tree, or calculate a hash function, or something else ... However, here we need to change only 2 values ​​(each element is included in exactly one “sqrt segment”)

int incElement(int index, int delta)
{
	A[index] += delta;
	sqrtSums[index/len] += delta;
}

Range Min / Max / Gcd Query

To answer RMQ queries (Range Min / Max Query) you need almost the same thing as for sums. However, it is worth noting that to update the element “stupidly”, it will take us time (when updating the element, recount min / max on the entire “sqrt segment”), but if we impose some restrictions on the updates, we will achieve an estimate . Namely, when solving the problem of finding the minimum / maximum, allow only to reduce / increase the element.
Code to update the minimum:

int decElement(int index, unsigned int delta) //delta - на сколько уменьшить элемент
{
	A[index] -= delta;
	sqrtSums[index/len] = min(sqrtSums[index/len], A[index]);
}

Similarly, to update the maximum:

int incElement(int index, unsigned int delta) //delta - на сколько увеличить элемент
{
	A[index] += delta;
	sqrtSums[index/len] = max(sqrtSums[index/len], A[index]);
}

It should be added that in the RMQ problem, the task does not reduce to [0; R] - [0; L-1], ie you’ll have to calculate the minimum / maximum from L to R (not counting the “sqrt segments” that are completely included in [L; R], think about why the asymptotic behavior will not change, and the net runtime may even improve ...).

To calculate the GCD (Greatest Common Divisor), we will not be able to use the "chip" that we turned for min / max. Therefore, both operations are calculated for .
Code for GCD (for minimum and maximum, getGCD functions will be replaced by 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++]);
}

Sources

Used this site, namely .
Since the lecture from the Kharkov Winter Computer School inspired the article, I ’ll throw the site , maybe soon there will be a collection for this year, with video lectures.

For now, I hope it was clear.