Square Root Decomposition or Mo's Algorithm
MO’s algorithm is just an order in which we process the queries. We were given M queries, we will re-order the queries in a particular order and then process them. Clearly, this is an offline algorithm. Each query has L and R, we will call them opening and closing. Let us divide the given input array into Sqrt(N) blocks (virtually) . Each block will be N / Sqrt(N) = Sqrt(N) size. Each opening has to fall in one of these blocks. Each closing has to fall in one of these blocks. How does the final order look like? All the queries are first ordered in ascending order of their block number (block number is the block in which its opening falls). Ties are ordered in ascending order of their R value. For example consider following queries and assume we have 3 blocks each of size 3. {0, 3} {1, 7} {2, 8} {7, 8} {4, 8} {4, 4} {1, 2} Let us re-order them based on their block number. (L/Block_size) {0, 3} {1, 7} {2, 8} {1, 2} {4, 8} {4, 4} {7, 8} Now let us re-order ties based on their R valu...