MO’s Algorithm - Square Root Decomposition

Square Root Decomposition

In this technique, we basically divide the given array into blocks of sqrt(N) elements. We chose sqrt(N) sized blocks so that size of each block as well as total blocks will be sqrt(N).
size of a block= $sqrt(N)$
total blocks = $N/sqrt(N)$ = $sqrt(N)$

We start by taking sum of each element that belongs to a block and putting the sum of ith block into a block array at the index i. This way ith block in block array will have sum of sqrt(N) elements of the given array beforehand. Now, whenever we process a query l to r, we add the block in the answer which is fully inside l to r in O(1) time and add those elements of range [l,r] individually which are partially included in the other blocks. So, in worst case scenerio we include all the sqrt(N) blocks for a given query in O(sqrt(N)) time. Worst case time complexity comes out to be O(sqrt(N)) which is efficient than naive approach.

let us consider an example of range sum query:

$Query: [L,R]=[1,6]$

There are 9 elements in the given array.
Block size : sqrt(9)=3.

We put the sum of every block in block array.

To process the query [1,6], we first find the block index of 1 and 6.

block index= (array_index)/(block_size)
block index of 1 = $1/3 = 0$
block index of 6 = $6/3 = 2$

We simply traverse from 1 to 6 and if a block is fully inside the given range i.e. block 1, we directly add its sum from the block array in O(1) time otherwise we add individual elements(arr[1], arr[2], arr[6]) by traversing the range.
initially, $sum=0$
Here 2 elements from block 0 are traversed:
$sum= 5 + (-2)= 3$
Block 1 is fully inside so take sum from block array: $sum= sum + block[1]= 3 + 7= 10$
1 element from block 2 is traversed:
$sum= 10 + 2= 12$
$sum= 12$

This way we efficiently answered the given query in O(sqrt(N)) time.

MO’s Algorithm

After learning sqrt decomposition, we can easily understand MO's algorithm. We are given Q range queries to answer. Suppose we answer the queries in order they are asked. So for every query we have to perform seperate traversal and find the answer. This will take O(N*Q) time where N is size of array and Q queries.

MO's algorithm states that sorting the queries in terms of L values and if same then in terms of R values will basically help the current query to be answered efficiently by taking the result of the previous query.

In other words, MO's algorithm is just an order in which we process the queries. Hence we should have the array of queries beforehand(offline queries).

MO's algorithm is only applicable to problems where:

• All the queries are known beforehand in the form of array so that we can sort them in our desired fashion.
• Queries dont update the given array i.e read only.
• If we know the answer of $[L,R]$ and we can compute the answer of $[L-1,R]$, $[L+1,R]$, $[L,R-1]$, $[L,R+1]$.

The idea of MO’s algorithm is to pre-process all queries so that result of one query can be used in next query.

• By sqrt decomposition we divide the array into blocks of sqrt(N) size. So, total blocks will be N/sqrt(N) = sqrt(N). There can be sqrt(N)+1 blocks if N is not a perfect square.
• We store the result(sum or mode) of every block in block array.
• We know that there are approx. $sqrt(N)$ blocks of size $sqrt(N)$.
  • we Sort the queries with L values from 0 to $sqrt(N)-1$ then $sqrt(N)$ to $2*sqrt(N)$ and so on.
  • All the queries within a block are sorted with their R values. By this we first sort queries in ascending order of the blocks and then if multiple queries lie in the same block then we sort them according to their R(right) values.
  • This scheme of sorting will help us in answering the current query by the use of previous query.
• Process all queries one by one in a way that every query uses the result computed in the previous query.
  • Lets say previous query was $[0,6]$ and the current query is $[2,9]$ then we subtract arr[0], arr[1] from the previous result and add arr[7], arr[8], arr[9] to the previous result.

Let's take the previous example:

Given an array of queries: Queries$[]$=$\{$ $[7,8]$, $[1,6]$, $[2,7]$ $\}$

We will sort these queries according to the following rule:

• Sort the queries in ascending order of their blocks in terms of their L(left) values and if multiple queries lie in same block then order the queries with respect to their R(right) values:
  • block array index of the ith element =index/total_blocks= i/sqrt(N)
  • range $[7,8]$ belongs to $7/sqrt(9)$= 2nd block
  • range $[1,6]$ belongs to $1/sqrt(9)$= 0th block
  • range $[2,7]$ belongs to $2/sqrt(9)$= 0th block
  • ranges $[1,6]$ and $[2,7]$ belongs to 0th block so we sort them by their R values. So their sorted order = ${ [1,6], [2,7] }$
  • Sorted order: Queries[]= $\{$ $[1,6]$, $[2,7]$, $[7,8]$ $\}$

Queries$[0]$=$[1,6]$ $Sum= arr[1] + arr[2] + block[1] + arr[6]$ $Sum= 3+7+2= 12$

• Queries$[1]$=$[2,7]$

PrevSum= 12 (from query[1,6])
$Sum = PrevSum - arr[1] + arr[7]$ $Sum = 12-5+1= 8$

• Queries$[2]$=$[7,8]$

PrevSum= 8 (from query[2,7])
Sum= PrevSum-arr[2]-arr[3]-arr[4]-arr[5]-arr[6]+arr[8] $Sum= 8-(-2)-6-8-(-7)-2+11$
$Sum= 12$

This way we efficiently used the past result to obtain new query result.

Implementation

Square Root Decompostion

• Firtly, take the array input in arr[N] with size N.
• Initialize the block array with size block$[sqrt(N)+1]$.
• Then put sum of subarrays of size sqrt(N) in block[ ].
  • block$[i/(sqrt(N)+1)]$ += arr[i]
• Now for each query input $[l,r]$ check if ith block is fully inside $[l,r]$.
  • if it is fully inside then add the sum from the block[ ].
  • else add individual elements from arr[ ].
• Ouput the calculated sum.

Complexity of sqrt Decomposition

Time Complexity: O(sqrt(N)). For answering a query [L,R] we jump onsqrt(N) blocks instead of every element of array. Space Complexity: O(sqrt(N)) extra space of block array to store preprocessed result.

MO's algorithm

• Firtly, take the array input in arr[N] with size N.
• Initialize the block size, block_len = sqrt(N)+1.
• Make a structure Query which will hold left value, right value and index of the query.
• Implement a comparator through which sort function will get the sorting technique. For two queries q1, q2:

• Initilize an array of structure of Queries q and take query input.
• Sort the queries with the help the above comparator function.
• Now, for each query maintain two pointers currL and currR which will point to range of previously answered query.
• Add or subtract the new elements to the currSum by the help currL and currR.
• Output the answer of each query in the same order they were asked.

Complexity of MO's algorithm

Time Complexity: $O((N+Q)*sqrt(N))$.

Sorting all queries will take $O(QlogQ)$.

Block size is $sqrt(N)$, so if we consider queries within the same block then the queries are sorted by right index. Therefore, in worst case we can say that currR is pointing to extreme right in a previous query and the current query wants the currR to shift to extreme left of the given array. This takes O(N) time to shift currR for queries within a single block. So, total time taken for all the blocks will be O(sqrt(N)*N).

And currL (curr left index) can change atmost sqrt(N) times for every new query. So total time taken by all the queries in changing currL is O(sqrt(N)*Q).

Total time complexity : $O((N+Q)*sqrt(N))$.

Space Complexity: O(Q) extra space to store the result of every query in offline mode.