This tutorial talks about Mo's algorithm using the SPOJ problem of DQUERY as an example. We see how we can process range queries offline to reduce overall time complexity.
The Mo's algorithm takes queries and sorts them in order of their range indexes. Arranging them in a clever way, we can ensure an O(sqrt(N)) time requirement per query. This allows us to solve many problems without any change in the logic of query solving.
We prove why sqrt(N) is the optimal block size, and take the example of DQUERY from SPOJ to understand the algorithm.
Problem statement:
[ Ссылка ]
Solution:
[ Ссылка ]
Here is an excellent blogpost by Anudeep Nekkanti on the same topic:
[ Ссылка ]
