**MO’s Algorithm** aka **Square Root Decomposition**, a very efficient and easy technique to solve **Range Query Problems (RQP). **For MO’s Algorithm to work, the **RQP** has to be **offline**. In this post, we will understand about RQP, Offline RPQ, Naive Approach to solve RQP and an Efficient Approach using MO’s Algorithm.

What is Range Query Problem?

You are given a sequence ** A **of

**values**

*N***. You also are given**

*A₁, A₂, A₃, …, Aₙ***queries. In each query, you will be given two values**

*Q***and**

*l***. Your task is to perform a function**

*r***on the elements in the subsequence**

*f(l, r)*

*Aₗ, Aₗ₊₁, …, Aᵣ₋₁, Aᵣ*## What is an Offline Query Problem?

An RQP is offline if it satisfies the following conditions

- All Queries are known beforehand.
- There are no update operations on the given sequence.

## Problem Statement

You are given a sequence ** A **of

**values**

*N***You also are given**

*A₁, A₂, A₃, …, Aₙ.***queries. Each query will have two values**

*Q***and**

*l***. Your task is to find the number of vowels in the range**

*r*

*Aₗ, Aₗ₊₁, …, Aᵣ₋₁, Aᵣ*## Naive Approach

A Simple approach is to iterate from ** l** to

**for each query**

*r***and find the number of vowels in the range. A sample code snippet is given below.**

*(l, r)***Time Complexity**The time complexity of the above code would be

**where**

*O(N*Q)***N = Number of elements in the Sequence**and

**Q = Number of Queries.**

## MO’s Algorithm

MO’s algorithm follows two simple steps to make the solution more efficient

- Divide the sequence into
*√N**blocks.* - Rearrange all the queries in such a way that a query
comes before*(l₁, r₁)*if*(l₂, r₂)*

By rearranging the queries in the above manner, we tend to process all the queries of one block before processing the queries of another block, thus minimizing the pointer movement of ** i** and

**Now, we apply MO’s technique in our problem.**

*j.*Now we have a sequence of letters of size 12. Now we apply the first step, calculate block size in our sequence

** BLOCK_SIZE = √12 ≈ 3, **So, we divide our sequence to 3 blocks each of size 4.

Now consider that the following queries are given to us *(4, 9), (3, 7), (2, 8), (0, 5), (7, 10), (1, 11)*

Out next step is to arrange the above queries based on **MO’s order. **The java code snippet for sorting logic is given below

Now the queries will be rearranged as* (0, 5), (2, 8), (1, 11), (3, 7), (4, 9), (7, 10)*

Now we process the queries in the new order

1. Initially, ** i**,

**, and**

*j***will be set to**

*vowelsCount***.**

*0*2. The whole idea is based on 2 observations

- While
**incrementing***i*we are excludingfrom our range and while*A[i]***decrementing**we are including*i*in our range.*A[i]* - While
**incrementing**we are including*j*from our range and while*A[j]***decrementing**we are including*j*in our range.*A[j]*

3. The first query is ** (0, 5)**.

**is in the right position. So, we increment**

*i***till it reaches**

*j***. While incrementing**

*5***if the letter present at**

*j***is vowel we increment**

*A[j]***.**

*vowelsCount*4. The next query is ** (2, 8)**. Currently,

**and j are in positions**

*i***and**

*0***respectively. So we increment**

*5***till it reaches**

*j***and increment**

*8***till it reaches index**

*i***2**. While incrementing

**, if the letter at**

*j***is a vowel we increment**

*A[j]***and while incrementing**

*vowelsCount,***, if the letter at**

*i***is a vowel we decrement**

*A[i]***.**

*vowelsCount*5. The next query is ** (1, 11)**. Currently,

**and**

*i***are in positions**

*j***and**

*2***respectively. So we increment**

*8***till it reaches**

*j***and decrement**

*11***till it reaches index**

*i***1**. While decrementing

**and while incrementing j, we increment**

*i we increment vowelsCount***.**

*vowelsCount*6. Similarly, we can adjust the pointer** i **and

**j**based on the remaining queries. The remaining steps are pictured below

Once all the queries are processed, we can print the result in the given order of queries.

**Time Complexity**

For each query, there are two movements one for pointer ** i **and another for pointer

*j***Movement of pointer ***i*

All queries are sorted in such a way that *l*** **values are grouped by blocks. So, we won’t move to the next block until we process all the queries in the current block. So, *i ***‘s **movement will be ** O(√N) **for each query. So for Q queries, the complexity will be

*O(Q * √N)***Movement of pointer ***j*

All queries are sorted in increasing order of *r***. **So, for a given block ** j **will be always increasing. So,

*j**can travel all the way up to*

**for each block**

*N***.**So the complexity will be

*O(N * √N)*So, the overall complexity will be *O(Q * √N) + O(N * √N) = O((N + Q) * √N)*

## Conclusion

MO’s algorithm will be very useful in competitive programming. You can find practice problems for MO’s Algorithms on codechef, SPOJ, codeforces, etc.

One of the famous problems is **DQUERY **from **SPOJ**

https://www.spoj.com/problems/DQUERY/

You can find the solution for the above problem in below Github URL