Mo's Algorithm

Offline range query processing with Hilbert curve ordering for optimal cache performance.

[Range Queries]|

Jul 9, 2026

|explanatory_notes.md|

#mo-algorithm#offline#range-query#hilbert-curve#two-pointers

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 5;
int a[MAXN], n, q;
ll ans;
ll answers[MAXN];

int64_t hilbert(int x, int y, int pw, int rot) {
    if (pw == 0) return 0;
    int hp = 1 << (pw - 1);
    int seg = (x < hp) ? ((y < hp) ? 0 : 3) : ((y < hp) ? 1 : 2);
    seg = (seg + rot) & 3;
    const int dr[] = {3, 0, 0, 1};
    int nx = x & (x ^ hp), ny = y & (y ^ hp);
    int64_t sub = int64_t(1) << (2 * pw - 2);
    int64_t add = hilbert(nx, ny, pw - 1, (rot + dr[seg]) & 3);
    return seg * sub + ((seg == 1 || seg == 2) ? add : sub - add - 1);
}

struct Query {
    int l, r, idx;
    int64_t ord;
    bool operator<(const Query &o) const { return ord < o.ord; }
};

void add(int idx) {
    // update ans when a[idx] enters range
}

void remove(int idx) {
    // update ans when a[idx] leaves range
}

void solve() {
    int pw = 1;
    while ((1 << pw) < n) pw++;

    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r; l--;
        queries[i] = {l, r - 1, i, hilbert(l, r - 1, pw, 0)};
    }
    sort(queries.begin(), queries.end());

    int cl = 0, cr = -1;
    for (auto &[l, r, qi, _] : queries) {
        while (cl > l) add(--cl);
        while (cr < r) add(++cr);
        while (cl < l) remove(cl++);
        while (cr > r) remove(cr--);
        answers[qi] = ans;
    }

    for (int i = 0; i < q; i++)
        cout << answers[i] << '\n';
}

58 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Mo's Algorithm

Process $q$ offline range queries on an array of size $n$ by reordering queries to minimize pointer movement.

How It Works

Sort queries by Hilbert curve order (better cache performance than block-based sorting)

Maintain two pointers

l

r

representing the current range

For each query, expand or shrink the range by calling add() / remove() to move pointers to the target

[l_i, r_i]

Record the answer after adjusting the range

Hilbert Curve Ordering

Traditional Mo's sorts by $(\lfloor l / \sqrt{n} \rfloor, r)$ . Hilbert curve ordering maps 2D coordinates $(l, r)$ to a 1D curve that preserves locality better, reducing total pointer movement by a constant factor.

When to Use

Offline range queries where add and remove are

O(1)

O(\log n)

Distinct element counting in ranges

Range frequency / mode queries

Any problem where you can maintain a running answer by adding/removing one element at a time

Implementation

Fill in add(idx) and remove(idx) with problem-specific logic

add should update the answer when element at idx enters the range

remove should update the answer when element at idx leaves the range

Complexity

Time —

O((n + q) \sqrt{n} \cdot f)

where

f

is the cost of add/remove

Space —

O(n + q)