**How To Search An Element In Sorted Matrix In Linear Time**

MO’s Algorithm aka Square Root Decomposition, a very efficient and easy technique to solve Range Query Problems (RQP) For the algorithm to work, the RQP has to be offline. In this post, we will understand about RQQP, Offline RPQ, Naive Approach, and an Efficient Approach using MO's Algorithm. For the problem, we are given a sequence A of N values A⁁, A₂, A , …, Aᵣ₋₁, apronounced A[j] is vowel.

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