Mo's algorithm

Useful for answering certain range queries on a static sequence. The algorithm works by maintaining some state for a current range, and updating the state by adding or removing elements one by one. An important parameter for the algorithm is the block size. If the range size is n, number of queries is q, block size is b, state update takes time f(n), getting the answer for the current state takes g(n), then the algorithm answers all queries in O(q log q + bq * f(n) + n^2/b * f(n) + q * g(n)) A suitable value of block size minimizes run time. For example, when q ~ n, f(n) = O(1), g(n) = O(1), setting b = sqrt(n) gives run time O(n sqrt(n)). For f(n) = O(log n), a better choice of b is sqrt(n/log n) giving run time O(n sqrt(n log n)). In practice, it works to experiment a bit and choose a good fixed value.

Sources:

• https://cp-algorithms.com/data_structures/sqrt_decomposition.html