aka , a very efficient and easy technique to solve For MO’s Algorithm to work, the has to be . 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? MO’s Algorithm Square Root Decomposition Range Query Problems (RQP). RQP offline You are given a sequence of values . You also are given queries. In each query, you will be given two values and . Your task is to perform a function on the elements in the subsequence A N A₁, A₂, A₃, …, Aₙ Q l r 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 of values You also are given queries. Each query will have two values and . Your task is to find the number of vowels in the range A N A₁, A₂, A₃, …, Aₙ. Q l r Aₗ, Aₗ₊₁, …, Aᵣ₋₁, Aᵣ Naive Approach A Simple approach is to iterate from to for each query and find the number of vowels in the range. A sample code snippet is given below. l r (l, r) The time complexity of the above code would be where and Time Complexity O(N*Q) N = Number of elements in the Sequence 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 if (l₁, r₁) (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 and Now, we apply MO’s technique in our problem. i j. Now we have a sequence of letters of size 12. Now we apply the first step, calculate block size in our sequence So, we divide our sequence to 3 blocks each of size 4. BLOCK_SIZE = √12 ≈ 3, 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 The java code snippet for sorting logic is given below MO’s order. 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, , , and will be set to . i j vowelsCount 0 2. The whole idea is based on 2 observations While we are excluding from our range and while we are including in our range. incrementing i A[i] decrementing i A[i] While we are including from our range and while we are including in our range. incrementing j A[j] decrementing j A[j] 3. The first query is . is in the right position. So, we increment till it reaches . While incrementing if the letter present at is vowel we increment . (0, 5) i j 5 j A[j] vowelsCount 4. The next query is . Currently, and j are in positions and respectively. So we increment till it reaches and increment till it reaches index . While incrementing , if the letter at is a vowel we increment and while incrementing , if the letter at is a vowel we decrement . (2, 8) i 0 5 j 8 i 2 j A[j] vowelsCount, i A[i] vowelsCount 5. The next query is . Currently, and are in positions and respectively. So we increment till it reaches and decrement till it reaches index . While decrementing and while incrementing j, we increment . (1, 11) i j 2 8 j 11 i 1 i we increment vowelsCount vowelsCount 6. Similarly, we can adjust the pointer and based on the remaining queries. The remaining steps are pictured below i j 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 and another for pointer i 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, movement will be for each query. So for Q queries, the complexity will be l i ‘s O(√N) O(Q * √N) Movement of pointer j All queries are sorted in increasing order of So, for a given block will be always increasing. So, can travel all the way up to for each block So the complexity will be r . j j N . 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 . You can find practice problems for MO’s Algorithms on , SPOJ, codeforces, etc. competitive programming codechef One of the famous problems is from DQUERY SPOJ https://www.spoj.com/problems/DQUERY/ You can find the solution for the above problem in below Github URL https://github.com/ganeshkumarm1/DSAlgo/tree/master/src/com/dsalgo/Algorithms/MOAlgorithm/DistinctVowels Thank you 🙏👋🤘 | Linkedin Github
