Mo’s Algorithm: Theory, Complexity, and Applications

1. Algorithm Overview

Mo’s Algorithm answers offline range queries on an array in O((N+Q) √N) time by reordering queries and maintaining a sliding window. Key steps:

1. Choose a block size B ≈ ⌊√N⌋.
2. Sort the Q queries by:
   1. ⌊L/B⌋ ascending,
   2. then R ascending if ⌊L/B⌋ is even, or descending if odd (optional “Hilbert” or “odd–even” trick).
3. Maintain current window [curL,curR] and a frequency/data structure. For each query [L,R] in this order:
   • While curL > L: add(--curL)
   • While curR < R: add(++curR)
   • While curL < L: remove(curL++)
   • While curR > R: remove(curR--)
   Then answer the query from your data structure.

Time Complexity

Each pointer (L or R) moves O(√N) per block of queries, for O(Q·√N + N·√N) ≈ O((N+Q)√N).

Memory Complexity

• O(N) to store the array and frequency counters.
• O(Q) to store queries and answers.

Total: O(N + Q).

---

2. Mathematics of Mo’s Algorithm

• Block decomposition: Divide indices 0…N–1 into blocks of size B ≈ √N. Then L moves block‐wise (N/B blocks), and R moves at most N per block ⇒ total pointer moves O(N·√N+Q·√N).
• Add/Remove operations: Each takes O(1) if you maintain a frequency array or simple counters.
• Optimal B: Minimizes O((N+Q)·B + Q·N/B). Setting B = √N yields balance: O((N+Q)√N).

---

3. Easy Problems

3.1 – Codeforces 86D “Powerful Array”

Given an array a[ ] and queries [L,R], compute ans = ∑ (cnt[x]² · x) over all values x in the subarray, where cnt[x] is the frequency of x.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct Query { int l, r, idx; };
int B;
bool cmp(const Query &a, const Query &b) {
    int ablock = a.l / B, bblock = b.l / B;
    if (ablock != bblock) return ablock < bblock;
    return (ablock & 1) ? (a.r > b.r) : (a.r < b.r);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    for(int i=0;i<N;i++) cin >> a[i];
    vector<Query> qs(Q);
    for(int i=0;i<Q;i++){
        cin >> qs[i].l >> qs[i].r;
        --qs[i].l; --qs[i].r;
        qs[i].idx = i;
    }

    B = max(1, (int)(sqrt(N)));
    sort(qs.begin(), qs.end(), cmp);

    vector<ll> ans(Q);
    vector<ll> freq(1000001);
    ll cur = 0;
    int curL = 0, curR = -1;

    auto add = [&](int x){
        ll &f = freq[x];
        cur -= f*f * x;
        ++f;
        cur += f*f * x;
    };
    auto remove = [&](int x){
        ll &f = freq[x];
        cur -= f*f * x;
        --f;
        cur += f*f * x;
    };

    for(auto &q : qs){
        while(curL > q.l) add(a[--curL]);
        while(curR < q.r) add(a[++curR]);
        while(curL < q.l) remove(a[curL++]);
        while(curR > q.r) remove(a[curR--]);
        ans[q.idx] = cur;
    }

    for(ll v : ans) cout << v << "\n";
    return 0;
}

Input:
5 3
1 2 1 3 2
1 3
2 5
1 5

Output:
6
12
19

3.2 – Codeforces 1514D “Cut”

Given array a[ ] of length N and Q queries [L,R], find the number of distinct elements in [L,R]. (Answer by maintaining freq[x] and a distinct‐count counter.)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Query { int l, r, idx; };
int B;
bool cmp(const Query &a, const Query &b){
    int ab = a.l / B, bb = b.l / B;
    if (ab != bb) return ab < bb;
    return ((ab & 1) ? (a.r > b.r) : (a.r < b.r));
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q; 
    cin >> N >> Q;
    vector<int> a(N);
    for(int i=0;i<N;i++) cin >> a[i];
    vector<Query> qs(Q);
    for(int i=0;i<Q;i++){
        cin >> qs[i].l >> qs[i].r;
        --qs[i].l; --qs[i].r;
        qs[i].idx = i;
    }

    B = max(1, (int)sqrt(N));
    sort(qs.begin(), qs.end(), cmp);

    vector<int> freq(1000001);
    vector<int> ans(Q);
    int curL = 0, curR = -1, distinct = 0;
    auto add = [&](int x){
        if (freq[x]++ == 0) ++distinct;
    };
    auto remove = [&](int x){
        if (--freq[x] == 0) --distinct;
    };

    for(auto &q : qs){
        while(curL > q.l) add(a[--curL]);
        while(curR < q.r) add(a[++curR]);
        while(curL < q.l) remove(a[curL++]);
        while(curR > q.r) remove(a[curR--]);
        ans[q.idx] = distinct;
    }

    for(int x : ans) cout << x << "\n";
    return 0;
}

Input:
7 3
1 2 1 3 2 2 4
2 4
1 7
3 5

Output:
2
4
2

---

4. Intermediate Problems

4.1 – Codeforces 375D “Tree and Queries”

Given a tree with colored nodes and queries (v, k), count how many colors appear at least k times in the subtree of v. Use Mo’s on tree (Euler tour to flatten subtree, then array intervals + Mo’s).

#include <iostream>
#include <vector>
#include <algorithm>>
using namespace std;
using ll = long long;

const int MAXN = 200005;
vector<int> g[MAXN];
int in[MAXN], out[MAXN], euler[2*MAXN], timer=0;
int color[MAXN];

void dfs(int u, int p){
    in[u] = timer; euler[timer++] = u;
    for(int v : g[u]) if(v!=p) dfs(v,u);
    out[u] = timer-1;
}

struct Query { int l, r, k, idx; };
int B;
bool cmp(const Query &a, const Query &b){
    int ab = a.l / B, bb = b.l / B;
    if(ab!=bb) return ab<bb;
    return ((ab&1)?(a.r>b.r):(a.r<b.r));
}

int cntColor[MAXN], cntFreq[MAXN];
int answer = 0;

void addNode(int u, int k){
    int c = color[u];
    cntFreq[cntColor[c]]--;
    if(++cntColor[c] == k) answer++;
    cntFreq[cntColor[c]]++;
}
void removeNode(int u, int k){
    int c = color[u];
    cntFreq[cntColor[c]]--;
    if(cntColor[c]-- == k) answer--;
    cntFreq[cntColor[c]]++;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    for(int i=1;i<=N;i++) cin >> color[i];
    for(int i=0,u,v;i<N-1;i++){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    vector<Query> qs(Q);
    for(int i=0;i<Q;i++){
        int v,k; cin >> v >> k;
        qs[i] = { in[v], out[v], k, i };
    }
    B = max(1,(int)sqrt(N));
    sort(qs.begin(), qs.end(), cmp);

    vector<int> res(Q);
    int curL = 0, curR = -1;
    for(auto &q : qs){
        while(curL > q.l) addNode(euler[--curL], q.k);
        while(curR < q.r) addNode(euler[++curR], q.k);
        while(curL < q.l) removeNode(euler[curL++], q.k);
        while(curR > q.r) removeNode(euler[curR--], q.k);
        res[q.idx] = answer;
    }

    for(int x : res) cout << x << "\n";
    return 0;
}

Input:
5 3
1 2 1 3 2
1 2
1 3
3 4
3 5
3 1
3 2
1 1

Output:
2
1
1

4.2 – Codeforces 208E “Blood Cousins”

Given a rooted tree with colored nodes, queries (v, k): how many nodes in v’s subtree have depth exactly depth[v]+k? Flatten subtree by depth‐indexed lists and answer each with binary search or Mo’s on list of depths.

#include <iostream>>
#include <vector>>
#include <algorithm>>
using namespace std;

const int MAXN = 200005;
vector<int> g[MAXN], byDepth[MAXN];
int in[MAXN], out[MAXN], depth[MAXN], timer=0;

void dfs(int u, int p){
    in[u] = timer++;
    byDepth[depth[u]].push_back(in[u]);
    for(int v : g[u]) if(v!=p){
        depth[v] = depth[u]+1;
        dfs(v,u);
    }
    out[u] = timer-1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    for(int i=2,p;i<=N;i++){
        cin >> p;
        g[p].push_back(i);
    }
    dfs(1,0);
    while(Q--){
        int v,k; cin >> v >> k;
        int d = depth[v] + k;
        auto &vec = byDepth[d];
        int l = lower_bound(vec.begin(),vec.end(), in[v]) - vec.begin();
        int r = upper_bound(vec.begin(),vec.end(), out[v]) - vec.begin();
        cout << (r - l) << "\n";
    }
    return 0;
}

Input:
5 3
1
1
3
3
1 1
3 1
3 2

Output:
2
2
0

---

5. Hard Problem

5.1 – Codeforces 940F “Machine Learning”

Maintain an array a[ ] under updates and range queries asking for the number of distinct elements in [L,R]. Use Mo’s Algorithm with modifications (“Mo’s with updates”): sort by (L/B, R/B, time/B).

#include <iostream>>
#include <vector>>
#include <algorithm>>
using namespace std;

struct Query{ int l,r,t,idx; };
struct Update{ int pos, prev, now; };

int B;
bool cmpQ(const Query &a, const Query &b){
    int ab = a.l/B, bb = b.l/B;
    if(ab!=bb) return ab<bb;
    int ar = a.r/B, br = b.r/B;
    if(ar!=br) return ar<br;
    return a.t < b.t;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,Q; cin >> N >> Q;
    vector<int> a(N);
    for(int i=0;i<N;i++) cin >> a[i];

    vector<Query> qs;
    vector<Update> us;
    int curTime=0;
    for(int i=0;i<Q;i++){
        int type; cin >> type;
        if(type==1){
            int p,x; cin >> p >> x; --p;
            us.push_back({p, a[p], x});
            a[p] = x;
        } else {
            int l,r; cin >> l >> r; --l; --r;
            qs.push_back({l,r,(int)us.size(), (int)qs.size()});
        }
    }

    B = max(1, (int)pow(N,2.0/3.0));
    sort(qs.begin(), qs.end(), cmpQ);

    vector<int> freq(1000001);
    vector<int> ans(qs.size());
    int curL=0, curR=-1, curT=0, distinct=0;

    auto add = [&](int x){ if(freq[x]++ == 0) ++distinct; };
    auto remove = [&](int x){ if(--freq[x] == 0) --distinct; };
    auto apply = [&](int t){
        int pos = us[t].pos, val = us[t].now;
        if(curL <= pos && pos <= curR){
            remove(us[t].prev);
            add(val);
        }
        a[pos] = val;
    };
    auto undo = [&](int t){
        int pos = us[t].pos, val = us[t].prev;
        if(curL <= pos && pos <= curR){
            remove(us[t].now);
            add(val);
        }
        a[pos] = val;
    };

    for(auto &q : qs){
        while(curT < q.t) apply(curT++);
        while(curT > q.t) undo(--curT);
        while(curL > q.l) add(a[--curL]);
        while(curR < q.r) add(a[++curR]);
        while(curL < q.l) remove(a[curL++]);
        while(curR > q.r) remove(a[curR--]);
        ans[q.idx] = distinct;
    }

    for(int x : ans) cout << x << "\n";
    return 0;
}

Input:
5 5
1 2 1 3 2
2 1 5
1 3 4
2 1 5
1 5 1
2 2 5

Output:
3
4
3