Sqrt-decomposition

Introduction

Today I would like to talk about the method of effectively calculating the sum of array elements from the lth to the rth . The most famous of these methods is the segment tree (RSQ), but it is rather difficult to write and understand, so I want to offer a simpler, but less effective, Sqrt decomposition.

Formal statement of the problem

Given an array of A [0..n-1], we need to learn how to effectively calculate the sum of the elements of A [l..r] for arbitrary l and r that are not beyond the limits of the array. Without loss of generality, we assume that l <= r .

Decision

Let's use the Sqrt-decomposition method. This method allows you to solve the problem for . The essence of the method is that we divide the source array into blocks of length and produce some pre-submission. It is obvious that such blocks will turn out pieces The last block may be shorter than the others if n is not completely divisible by but there is nothing scary about it.
')
Let block length len = (we will assume that the root value is rounded up).


And if n is not divided by len , then the length of the last block will be not len , but less. That, as mentioned earlier, is not critical.

Next, create an array B, in B [i] we will store the sum of the elements of the i-th block. Obviously, such a pre-submission will take time, so we just need to run once through the array A.

Therefore, when requesting a sum, we do not need to run through all the elements of the array from l to r , since we have already calculated partial sums. Consider an example.

Let A = {3, 4, 8, 7, 1, 6, 1, 6}, then len = 3, B [0] = 15, B [1] = 14, B [2] = 7.
And they ask us the sum of the elements from the 1st to the 6th (we number them from zero).



First, we have to honestly run through the two elements of the array and add 4 and 8, because we do not need the full sum B [0], but only a part. Next, we do not need to run through the array, since B [1] is already counted and equals 14, well, finally, add 1, also running, as it were, since we need not the full amount of the last block.

Implementation:

// We have an array A (specified) and B is an array of partial sums.
// len - block length

for (int i = 0; i <n; i ++)
B [i / len] + = A [i]; // Calculate the amount of blocks

// l and r - borders

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

The sum will be the result.

Another advantage of this method is that we can very easily change the elements of an array. When changing the element of the array A, we just need to recalculate the element from B, where the variable element lies. This obviously needs operations. Also, this method can be used to calculate the minimum and maximum on the segment of the array. To do this, you need to store in B the minima and maxima of the corresponding blocks.