MO’s Algorithm — Range Queries Made Easy

MO’s Algorithm — Range Queries Made Easy

An Efficient Way to Solve Offline Range Query Problems 😏

Ganesh Kumar Marimuthu's photo
Ganesh Kumar Marimuthu
·Aug 4, 2020·

5 min read

Subscribe to my newsletter and never miss my upcoming articles

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 N values A₁, A₂, A₃, …, Aₙ. You also are given Q queries. In each query, you will be given two values l and r. Your task is to perform a function f(l, r) on the elements in the subsequence Aₗ, Aₗ₊₁, …, Aᵣ₋₁, Aᵣ

What is an Offline Query Problem?

An RQP is offline if it satisfies the following conditions

  1. All Queries are known beforehand.

  2. There are no update operations on the given sequence.

Problem Statement

You are given a sequence A of N values A₁, A₂, A₃, …, Aₙ. You also are given Q queries. Each query will have two values l and r. Your task is to find the number of vowels in the range Aₗ, Aₗ₊₁, …, Aᵣ₋₁, Aᵣ

Naive Approach

A Simple approach is to iterate from l to r for each query (l, r) and find the number of vowels in the range. A sample code snippet is given below.

Java Code Snippet for Naive ApproachJava 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

  1. Divide the sequence into *√N blocks.*

  2. Rearrange all the queries in such a way that a query (l₁, r₁) comes before (l₂, r₂) if

MO’s Order ConditionsMO’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 j. Now, we apply MO’s technique in our problem

Sample SequenceSample 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 blocksSequence 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 LogicCode 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

  1. Initially, i, j, and vowelsCount will be set to 0.

  2. 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.
  1. The first query is (0, 5). i is in the right position. So, we increment j till it reaches 5. While incrementing j if the letter present at A[j] is vowel we increment vowelsCount.

Process query (0, 5)Process query (0, 5)

  1. The next query is (2, 8). Currently, i and j are in positions 0 and 5 respectively. So we increment j till it reaches 8 and increment i till it reaches index 2. While incrementing j, if the letter at A[j] is a vowel we increment vowelsCount, and while incrementing i, if the letter at A[i] is a vowel we decrement vowelsCount.

Process query (2, 8)Process query (2, 8)

  1. The next query is (1, 11). Currently, i and j are in positions 2 and 8 respectively. So we increment j till it reaches 11 and decrement i till it reaches index 1. While decrementing i we increment vowelsCount and while incrementing j, we increment vowelsCount.

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

Process Query (3, 7)Process Query (3, 7)

Process Query (4, 9)Process Query (4, 9)

Process Query (7, 10)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 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 **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

 
Share this

Impressum

To know more about me, visit ganeshkumarm.me 😉