# MO’s Algorithm — Range Queries Made Easy

## An Efficient Way to Solve Offline Range Query Problems 😏

Photo by Arian Darvishi on Unsplash

**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 a 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)**Java Code Snippet for Naive Approach*

**Time Complexity
**The time complexity of the above code would be ** O(NQ)*** where

**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₂)*

*MO’s Order Conditions*

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.**Sample Sequence*

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.

*Sequence divided into √N blocks*

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

*Code Snippet for Soring Logic*

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

Initially,

,*i*, and*j*will be set to*vowelsCount*.*0*The whole idea is based on 2 observations

```
a. While **incrementing** ***i ***we are excluding ***A[i]*** from our range and while **decrementing *i*** we are including ***A[i]*** in our range.
b. While **incrementing *j ***we are including ***A[j]*** from our range and while **decrementing *j*** we are including ***A[j]*** in our range.
```

- 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*

*Process query (0, 5)*

- The next query is
. Currently,*(2, 8)*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*

*Process query (2, 8)*

- The next query is
. Currently,*(1, 11)*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 decrementingand while incrementing j, we increment*i we increment vowelsCount*.*vowelsCount*

- Similarly, we can adjust the pointer
and*i***j**based on the remaining queries. The remaining steps are pictured below

*Process Query (3, 7)*

*Process Query (4, 9)*

*Process Query (7, 10)*

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

**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,**

*l***movement will be**

*i*‘s**for each query. So for Q queries, the complexity will be**

*O(√N)*

*O(Q*√N)***Movement of pointer j
**All queries are sorted in increasing order of

**So, for a given block**

*r*.**will be always increasing. So,**

*j****j**

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

***for each block**.

**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**
**SPOJ.com - Problem DQUERY**
*Đọc đề đẹp hơn ở: codeforces.com/group/FLVn1Sc504/contest/274.. Given a sequence of n numbers a 1, a…*spoj.com

You can find the solution for the above problem in below Github URL
**ganeshkumarm1/DSAlgo**
*Contribute to ganeshkumarm1/DSAlgo development by creating an account on GitHub.*github.com

## Thank you 🤘

To know more about me, visit ganeshkumarm.me