Mo's Algorithm

Mo's Algorithm is a powerful offline technique used to solve range query problems. It is particularly effective when the query results can be updated incrementally as we shift the query boundaries [L, R] to [L', R'].

The Intuition

The idea is to sort the queries in a specific order so that the total movement of the L and R pointers is minimized. By dividing the array into blocks of size sqrt(N), we can process queries in O((N+Q) * sqrt(N)) time.

Java Implementation Strategy

To use Mo's Algorithm:

1. Divide the array into blocks of size B = sqrt(N).
2. Sort the queries primarily by the block of their left endpoint L/B, and secondarily by their right endpoint R.
3. Move the L and R pointers to match each query, adding or removing elements as you go.

import java.util.*;

class Query implements Comparable<Query> {
    int L, R, id, block;
    public Query(int L, int R, int id, int blockSize) {
        this.L = L;
        this.R = R;
        this.id = id;
        this.block = L / blockSize;
    }
    public int compareTo(Query other) {
        if (this.block != other.block) return Integer.compare(this.block, other.block);
        return Integer.compare(this.R, other.R);
    }
}

Why it matters

• Efficient Range Queries: Handles problems where no easy "inverse operation" (like subtraction for sum queries) exists.
• Flexibility: Great for frequency counting, distinct elements, or complex range statistics.

Complexity

• Time: O((N+Q) * sqrt(N)) where N is the array size and Q is the number of queries.
• Space: O(N + Q) for the array and queries.