Chapter 93

Home

Mo's Algorithm

Mo's algorithm answers offline range queries by cleverly reordering them. When the answer can be extended one element at a time, sorting queries by (block of L, R) reduces pointer movement from O(N×Q) to O((N+Q)√N).

Mo's Algorithm for Range Frequency

C++ — Mo's algorithm for range distinct count

struct Query { int l, r, idx; };

vector mo(vector& arr, vector& queries) {
    int n = arr.size(), B = sqrt(n) + 1;

    sort(queries.begin(), queries.end(), [B](auto& a, auto& b) {
        int ba = a.l / B, bb = b.l / B;
        if (ba != bb) return ba < bb;
        return (ba & 1) ? (a.r > b.r) : (a.r < b.r);  // hilbert-ish
    });

    vector freq(1000001, 0), ans(queries.size());
    int cur_l = 0, cur_r = -1, cur_ans = 0;

    auto add = [&](int pos) {
        if (++freq[arr[pos]] == 1) cur_ans++;
    };
    auto remove = [&](int pos) {
        if (--freq[arr[pos]] == 0) cur_ans--;
    };

    for (auto& q : queries) {
        while (cur_l > q.l) add(--cur_l);
        while (cur_r < q.r) add(++cur_r);
        while (cur_l < q.l) remove(cur_l++);
        while (cur_r > q.r) remove(cur_r--);
        ans[q.idx] = cur_ans;
    }
    return ans;
}

// O((N+Q)√N) — great for 10⁵ queries on 10⁵ elements

💡 Mo's is offline only

You need all queries upfront. If updates are involved, use Mo's with updates (3D Mo) instead. The odd/even block sort trick reduces R-pointer movement by keeping it zigzagging.

Key Takeaways