## Introduction

If you are into sports then competitive programming is definitely for you, the only difference here is that it is more of a mind sport where you have to solve complex problems using complex algorithms. Today, we will discuss one such algorithm, i.e., Mo’s Algorithm, and see how it differs from the famous sqrt decomposition method.

## Sqrt Decomposition

Preprocessing is the basic concept of sqrt decomposition. We'll partition the array ‘a’ into blocks of roughly length sqrt(N) and precalculate the sum of the elements in each of the blocks. Let's say for a block, ‘k’ sum is b[k]. We will find the value of b[k] using the formula given below.

As a result, we've figured out the values of b[k](this will cost us O(N) operations). But how can they assist us in answering the range queries [l,r]?

If the interval [l, r] is long enough, it will contain numerous full blocks, and we may find the sum of their elements in a single operation for those blocks. As a result, the interval will only contain parts of two blocks, and the sum of elements in these parts will be straightforward to calculate.

But how?

We only need sum of the two tail elements that are

We can use the formula below to solve the problem

These formulas must be very confusing for you. Don't worry. Once you look at its implementation, things will become easier.

### Code

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
/*Input */
int n;
cin >> n;
vector<int> a(n, 0);
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
a[i] = x;
}
/*Precalculations.*/
int sqrtValue = (int) sqrt(n + .0);
/*This is the size of one block */
int len = sqrtValue + 1;
vector<int> b;
b.resize(len);
/*Finding sums */
for (int i = 0; i < n; ++i)
b[i / len] += a[i];
int q;
cin >> q;
/*Queries*/
for (int i = 0; i < q; i++)
{
int l, r;
cin >> l >> r;
int sum = 0;
for (int i = l; i <= r;)
if (i + len - 1 <= r && i % len == 0)
{ /*If the complete block 'i' belongs to[l,r]*/
sum = sum + b[i / len];
i = i + len;
}
else
{
sum += a[i];
++i;
}
cout << sum << endl;
}
}
```

#### Input

```
9
1 1 2 1 3 4 5 2 8
3
0 4
1 3
2 4
```

#### Output

```
8
6
4
```

### Complexities

#### Time Complexity

**O(Q * sqrt(N))**, where ‘N’ is the size of the array and ‘Q’ is the number of queries.

**Reason**: We are first pre-processing the sums that will cost us O(N) time then we for every query we will run a loop from ‘L’ to ‘R’ which even in the worst case will cost us O(sqrt(N)) time. Thus, the overall time complexity to O(Q * sqrt(N)) + O(N) ~ O(Q * sqrt(N)).

#### Space Complexity

**O(N)**, where ‘N’ is the size of the array.

**Reason**: This is the space used by sum array ‘b’.

Read More - __Time Complexity of Sorting Algorithms__

Check out __Euclid GCD Algorithm__