Mo's Algorithm

Answering many offline range queries efficiently by reordering them to minimize the movement of two pointers.

Offline query reordering

Mo's algorithm answers q range queries on a static array by processing them offline in a carefully chosen order so that a running window can be adjusted incrementally. Instead of recomputing each range from scratch, it maintains an answer for the current window [l, r] and slides the endpoints to the next query. The reordering bounds the total pointer movement.

Block ordering

Queries are sorted by the block of their left endpoint (blocks of size about sqrt(n)), and within a block by right endpoint. With this order, the right pointer moves monotonically within each block and the left pointer stays within one block at a time. Total movement is O((n + q) * sqrt(n)), so each query costs about O(sqrt(n)) amortized, provided add and remove of a single element are O(1).

Comparator and loop

python

import math

def mos(queries, n):
    block = int(math.sqrt(n)) + 1
    queries.sort(key=lambda q: (q.l // block,
                                q.r if (q.l//block) % 2 == 0 else -q.r))
    cl, cr = 0, -1
    for q in queries:
        while cr < q.r: cr += 1; add(cr)
        while cl > q.l: cl -= 1; add(cl)
        while cr > q.r: remove(cr); cr -= 1
        while cl < q.l: remove(cl); cl += 1
        q.answer = current_answer()

Requirements and variants

• Needs cheap incremental add and remove of one element (distinct-count, frequency, sum).
• Queries must be offline (all known in advance) and the array static.
• Mo's on trees flattens the tree with an Euler tour first.
• Mo's with updates adds a time dimension for O(n^(5/3)) with modifications.

When to use it

Reach for Mo's algorithm when a query cannot be decomposed by a segment tree (for example, count of distinct values in a range) but can be maintained incrementally, and all queries are known ahead of time.