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

Kronos motion — classical

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.