**Register Now!**

413 reads

by Ganesh Kumar MAugust 18th, 2020

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

An RQP is offline if it satisfies the following conditions

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

You are given a sequence ** A **of

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

**Time Complexity**The time complexity of the above code would be

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

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

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

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

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

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

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

**Movement of pointer ***j*

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

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

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

L O A D I N G

. . . comments & more!

. . . comments & more!