SQRT Decomposition
Sqrt-decomposition is an approach to implement associative operations (e.g., summing elements, finding the minimum/maximum, etc.) on consecutive elements of some set of size in per query.
Let an array of size be given. We perform the following steps:
If we choose , then .
Complexity:
Suppose we receive a query to perform an operation on the segment . The segment can cover some blocks of the array completely, and at most two blocks (initial and final) — not completely.
Thus, in order to find the result of an operation on the segment , it is necessary to perform it manually on the “tails”, and then combine this with the precomputed values of the full blocks.
Below is the example for the segment :
Complexity:
When an element at position is updated to a new value, we must update the corresponding block value in .
The element belongs to block
After changing , we recompute the aggregate value of that block.
Complexity:
for (int i = 0; i < M; i++) {
b[i] = 0;
for (int j = i * K; j < min(N, (i + 1) * K); j++) {
b[i] = b[i] + a[j];
}
}
int query(int l, int r) {
int left_block = l / K;
int right_block = r / K;
int res = 0;
if (left_block == right_block) {
for (int i = l; i <= r; i++) {
res += a[i];
}
} else {
for (int i = l; i < (left_block + 1) * K; i++) {
res += a[i];
}
for (int i = left_block + 1; i < right_block; i++) {
res += b[i];
}
for (int i = right_block * K; i <= r; i++) {
res += a[i];
}
}
return res;
}
void update(int i, int new_a) {
int block = i / K;
a[i] = new_a;
b[block] = 0;
for (int j = block * K; j < min(N, (block + 1) * K); j++) {
b[block] += a[j];
}
}