AntInLoop

Mo's Algorithm (Offline Range Queries)

Mo's Algorithm answers static offline range queries in O((N + Q) sqrt(N)) time by sorting queries into sqrt(N)-sized blocks and maintaining a sliding window with O(1) add/remove transitions.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Mo's Algorithm (Offline Range Queries)

Mo's Algorithm answers $Q$ offline static range queries [L, R] on an array of size $N$ in $O((N + Q)\sqrt{N})$ time—even for queries like "number of distinct values in [L, R]" or *"sum of freq[x]^2 x"** that cannot be merged in a Segment Tree! The secret is sorting the queries by (L / B, R) (with $B \approx \sqrt{N}$) so that a single sliding window [curL, curR] moves only $O((N + Q)\sqrt{N})$ total steps across all queries.

At a Glance

| Property | Value |

| :--- | :--- |

| Time Complexity | $O((N + Q)\sqrt{N} \cdot T_{\text{add/remove}})$ |

| Auxiliary Space | $O(N + Q)$ |

| Requires Offline Queries? | Yes (all queries must be known in advance; no updates in basic Mo's) |

| Best Used When | Range distinct count, range frequency queries, subtree queries via Euler Tour |

---

How It Works

1. Choose block size $B = \max(1, \lfloor N / \sqrt{Q} \rfloor)$ (or $\lfloor \sqrt{N} \rfloor$).

2. Sort queries by L / B ascending, and within the same block by R ascending (or alternating ascending/descending for odd/even snake order, cutting R movement in half!).

3. Maintain [curL, curR] initialized to [0, -1]. For each query (L, R):

  • Expand before shrinking so curL <= curR + 1 stays valid:
  • while (curL > L) add(--curL);
  • while (curR < R) add(++curR);
  • while (curL < L) remove(curL++);
  • while (curR > R) remove(curR--);
  • Store the current answer at ans[q.id].

---

Complexity & Key Insights

  • Why Total Pointer Movement Is $O((N + Q)\sqrt{N})$:
  • curL moves at most $B$ per query within a block and jumps across blocks at most $N / B$ times → $O(Q \cdot B + N)$ total.
  • Within each of the $N / B$ blocks, R is sorted monotonically, so curR sweeps at most $N$ per block → $O(N^2 / B)$ total.
  • Setting $B = \sqrt{N}$ balances both to $O((N + Q)\sqrt{N})$!
  • Always Expand First: Expanding curL/curR before shrinking guarantees the window never becomes inverted (curL > curR + 1), preventing negative frequencies in remove().

---

Practice Problems

Easy

1. Number of Distinct Elements in Range $[L, R]$ (SPOJ DQUERY)

Answer $Q$ offline queries asking for the number of distinct integers in a[L..R].

Approach: Maintain freq[val] and distinct. Increment distinct when ++freq[val] == 1; decrement when --freq[val] == 0. Time: $O((N + Q)\sqrt{N})$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

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

std::vector<int> moDistinct(const std::vector<int>& a, std::vector<Query> queries) {
    int n = static_cast<int>(a.size());
    int B = std::max(1, static_cast<int>(std::sqrt(n)));
    std::sort(queries.begin(), queries.end(), [B](const Query& x, const Query& y) {
        int bx = x.l / B, by = y.l / B;
        if (bx != by) return bx < by;
        return (bx & 1) ? (x.r > y.r) : (x.r < y.r);
    });

    int maxVal = *std::max_element(a.begin(), a.end());
    std::vector<int> freq(maxVal + 1, 0), ans(queries.size());
    int curL = 0, curR = -1, distinct = 0;

    auto add = [&](int idx) { if (++freq[a[idx]] == 1) ++distinct; };
    auto rem = [&](int idx) { if (--freq[a[idx]] == 0) --distinct; };

    for (const auto& q : queries) {
        while (curL > q.l) add(--curL);
        while (curR < q.r) add(++curR);
        while (curL < q.l) rem(curL++);
        while (curR > q.r) rem(curR--);
        ans[q.id] = distinct;
    }
    return ans;
}

int main() {
    auto res = moDistinct({1, 1, 2, 1, 3, 2}, {{0, 3, 0}, {1, 4, 1}, {2, 5, 2}});
    for (int x : res) std::cout << x << " ";
    std::cout << "\n"; // 2 3 3
    return 0;
}

</details>

2. Range Sum of Squares of Frequencies (Codeforces 86D — Powerful Array)

For each query [L, R], compute $\sum_v \text{freq}(v)^2 \cdot v$.

Approach: When adding v, freq[v] goes from c to c + 1, changing the sum by (2c + 1) v. When removing v, freq[v] goes from c to c - 1, changing the sum by -(2c - 1) v. Both are $O(1)$!

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

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

std::vector<long long> powerfulArray(const std::vector<int>& a, std::vector<Query> queries) {
    int n = static_cast<int>(a.size());
    int B = std::max(1, static_cast<int>(std::sqrt(n)));
    std::sort(queries.begin(), queries.end(), [B](const Query& x, const Query& y) {
        int bx = x.l / B, by = y.l / B;
        if (bx != by) return bx < by;
        return (bx & 1) ? (x.r > y.r) : (x.r < y.r);
    });

    int maxVal = *std::max_element(a.begin(), a.end());
    std::vector<long long> freq(maxVal + 1, 0), ans(queries.size());
    int curL = 0, curR = -1;
    long long power = 0;

    auto add = [&](int idx) {
        long long v = a[idx];
        power += (2 * freq[v] + 1) * v;
        ++freq[v];
    };
    auto rem = [&](int idx) {
        long long v = a[idx];
        --freq[v];
        power -= (2 * freq[v] + 1) * v;
    };

    for (const auto& q : queries) {
        while (curL > q.l) add(--curL);
        while (curR < q.r) add(++curR);
        while (curL < q.l) rem(curL++);
        while (curR > q.r) rem(curR--);
        ans[q.id] = power;
    }
    return ans;
}

int main() {
    auto res = powerfulArray({1, 2, 1}, {{0, 1, 0}, {0, 2, 1}});
    for (long long x : res) std::cout << x << " ";
    std::cout << "\n"; // 3 (1*1 + 1*2), 6 (4*1 + 1*2)
    return 0;
}

</details>

---

Intermediate

3. Count Elements Whose Frequency Equals Their Value (Codeforces 220B — Little Elephant)

For each query [L, R], count how many distinct integers $x$ appear exactly $x$ times in a[L..R].

Approach: Ignore values

Loading AntInLoop...

gt; N$ (they can never appear $x$ times in an array of length $N$). Update good in $O(1)$ whenever freq[v] enters or leaves v. Time: $O((N + Q)\sqrt{N})$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

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

std::vector<int> countFreqEqualsVal(const std::vector<int>& a, std::vector<Query> queries) {
    int n = static_cast<int>(a.size());
    int B = std::max(1, static_cast<int>(std::sqrt(n)));
    std::sort(queries.begin(), queries.end(), [B](const Query& x, const Query& y) {
        int bx = x.l / B, by = y.l / B;
        if (bx != by) return bx < by;
        return (bx & 1) ? (x.r > y.r) : (x.r < y.r);
    });

    std::vector<int> freq(n + 1, 0), ans(queries.size());
    int curL = 0, curR = -1, good = 0;

    auto add = [&](int idx) {
        int v = a[idx];
        if (v > n) return;
        if (freq[v] == v) --good;
        if (++freq[v] == v) ++good;
    };
    auto rem = [&](int idx) {
        int v = a[idx];
        if (v > n) return;
        if (freq[v] == v) --good;
        if (--freq[v] == v) ++good;
    };

    for (const auto& q : queries) {
        while (curL > q.l) add(--curL);
        while (curR < q.r) add(++curR);
        while (curL < q.l) rem(curL++);
        while (curR > q.r) rem(curR--);
        ans[q.id] = good;
    }
    return ans;
}

int main() {
    auto res = countFreqEqualsVal({3, 1, 2, 2, 3, 3, 7}, {{0, 5, 0}, {1, 3, 1}});
    for (int x : res) std::cout << x << " ";
    std::cout << "\n"; // 3 (1,2,3), 2 (1,2)
    return 0;
}

</details>

4. Range Mode Frequency (Maximum Frequency in $[L, R]$)

For each offline query [L, R], find the highest frequency of any element in a[L..R].

Approach: Maintain freq[v], cntOfFreq[f] (how many distinct values currently have frequency f), and maxFreq. On add, maxFreq can only increase by 1; on remove, if cntOfFreq[maxFreq] drops to 0, decrement maxFreq by 1! Both remain $O(1)$!

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

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

std::vector<int> moMaxFreq(const std::vector<int>& a, std::vector<Query> queries) {
    int n = static_cast<int>(a.size());
    int B = std::max(1, static_cast<int>(std::sqrt(n)));
    std::sort(queries.begin(), queries.end(), [B](const Query& x, const Query& y) {
        int bx = x.l / B, by = y.l / B;
        if (bx != by) return bx < by;
        return (bx & 1) ? (x.r > y.r) : (x.r < y.r);
    });

    int maxVal = *std::max_element(a.begin(), a.end());
    std::vector<int> freq(maxVal + 1, 0), cntOfFreq(n + 2, 0), ans(queries.size());
    int curL = 0, curR = -1, maxF = 0;

    auto add = [&](int idx) {
        int v = a[idx];
        int f = freq[v];
        if (f > 0) --cntOfFreq[f];
        ++freq[v];
        ++cntOfFreq[f + 1];
        if (f + 1 > maxF) maxF = f + 1;
    };
    auto rem = [&](int idx) {
        int v = a[idx];
        int f = freq[v];
        --cntOfFreq[f];
        --freq[v];
        if (f - 1 > 0) ++cntOfFreq[f - 1];
        if (f == maxF && cntOfFreq[f] == 0) --maxF;
    };

    for (const auto& q : queries) {
        while (curL > q.l) add(--curL);
        while (curR < q.r) add(++curR);
        while (curL < q.l) rem(curL++);
        while (curR > q.r) rem(curR--);
        ans[q.id] = maxF;
    }
    return ans;
}

int main() {
    auto res = moMaxFreq({1, 2, 1, 3, 2, 2, 1}, {{0, 3, 0}, {1, 5, 1}, {0, 6, 2}});
    for (int x : res) std::cout << x << " ";
    std::cout << "\n"; // 2 3 3
    return 0;
}

</details>

---

Hard

5. Distinct Colors in Every Subtree (Euler Tour + Mo's Algorithm)

Given a rooted tree where each node has a color, answer offline queries: how many distinct colors appear in the subtree of node u?

Approach: Run an Euler Tour DFS recording tin[u] and tout[u] to flatten the tree into an array flat[0..n-1]. Every subtree u maps to the contiguous interval [tin[u], tout[u]]—so standard Mo's Algorithm answers all subtree queries in $O((N + Q)\sqrt{N})$!

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

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

int main() {
    int n = 6;
    std::vector<int> color = {1, 2, 1, 3, 2, 4};
    std::vector<std::vector<int>> adj(n);
    auto addEdge = [&](int u, int v) { adj[u].push_back(v); adj[v].push_back(u); };
    addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(1, 4); addEdge(2, 5);

    std::vector<int> tin(n), tout(n), flat(n);
    int timer = 0;
    auto dfs = [&](auto& self, int u, int p) -> void {
        tin[u] = timer;
        flat[timer++] = color[u];
        for (int v : adj[u]) if (v != p) self(self, v, u);
        tout[u] = timer - 1;
    };
    dfs(dfs, 0, -1);

    std::vector<int> askNodes = {0, 1, 2};
    std::vector<Query> queries;
    for (int i = 0; i < static_cast<int>(askNodes.size()); ++i) {
        queries.push_back({tin[askNodes[i]], tout[askNodes[i]], i});
    }

    int B = std::max(1, static_cast<int>(std::sqrt(n)));
    std::sort(queries.begin(), queries.end(), [B](const Query& x, const Query& y) {
        if (x.l / B != y.l / B) return x.l / B < y.l / B;
        return x.r < y.r;
    });

    std::vector<int> freq(10, 0), ans(queries.size());
    int curL = 0, curR = -1, distinct = 0;
    auto add = [&](int i) { if (++freq[flat[i]] == 1) ++distinct; };
    auto rem = [&](int i) { if (--freq[flat[i]] == 0) --distinct; };

    for (const auto& q : queries) {
        while (curL > q.l) add(--curL);
        while (curR < q.r) add(++curR);
        while (curL < q.l) rem(curL++);
        while (curR > q.r) rem(curR--);
        ans[q.id] = distinct;
    }

    for (int x : ans) std::cout << x << " ";
    std::cout << "\n"; // subtree(0)=4, subtree(1)=2 ({2,3}), subtree(2)=2 ({1,4})
    return 0;
}

</details>

---

Related Algorithms