Mo's Algorithm and Offline Queries

Query ordering, block decomposition, add/remove functions, time complexity intuition, modifications/time dimension, and when offline processing is possible.

Query ordering, block decomposition, add/remove functions, time complexity intuition, modifications/time dimension, and when offline processing is possible. Include examples such as distinct count and frequency-power queries.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Sorting queries by (block of l, r) keeps the right pointer moving monotonically within a block (O(n) per block, √n blocks) and the left pointer moving O(√n) per query: O((n + Q)√n) total add/remove calls. It requires all queries in advance (offline) and cheap add/remove. Mo's with updates adds a time dimension and blocks of size about n^(2/3).

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

int main() {
    mt19937 rng(13);
    int n = 2000, Q = 2000;
    vector<int> a(n); for (int& x : a) x = rng() % 50;
    vector<array<int, 3>> qs(Q);                                     // l, r (inclusive), index
    for (int i = 0; i < Q; ++i) { int l = rng() % n, r = rng() % n; if (l > r) swap(l, r); qs[i] = {l, r, i}; }
    int B = max(1, (int)sqrt(n));
    sort(qs.begin(), qs.end(), [&](auto& x, auto& y) {
        if (x[0] / B != y[0] / B) return x[0] / B < y[0] / B;
        return (x[0] / B) % 2 ? x[1] > y[1] : x[1] < y[1];           // alternate direction: fewer pointer moves
    });
    vector<int> cnt(50, 0), ans(Q); int distinct = 0, L = 0, R = -1; long long moves = 0;
    auto add = [&](int i) { if (cnt[a[i]]++ == 0) ++distinct; ++moves; };
    auto remove = [&](int i) { if (--cnt[a[i]] == 0) --distinct; ++moves; };
    for (auto [l, r, idx] : qs) {
        while (R < r) add(++R);
        while (L > l) add(--L);
        while (R > r) remove(R--);
        while (L < l) remove(L++);
        ans[idx] = distinct;
    }
    for (auto [l, r, idx] : qs) {
        set<int> s(a.begin() + l, a.begin() + r + 1);
        if ((int)s.size(
…

2000 distinct-count queries on n = 2000 match direct counting
pointer moves with Mo's order: 75826 (about (n + Q) * sqrt(n) = 176000; answering each query from scratch could need up to n*Q = 4000000)

Quiz

? Why does Mo's algorithm sort queries by the block of their left endpoint?
+ Within a block the right pointer moves monotonically, bounding total movement to O((n + Q)√n). :: Sorting is the whole trick.
- To answer queries in input order. :: The answers are written back by index.
- Because l must be smaller than r. :: Unrelated.
- To use binary search. :: No.

? What does Mo's algorithm require?
+ All queries known in advance, and O(1)-ish add/remove of one element :: Offline processing.
- Updates between queries :: Plain Mo's has none (Mo's with updates exists).
- A sorted array :: No.
- An invertible operation :: Not necessarily — distinct count is not invertible by prefix difference.

? Alternating the r order between odd and even blocks…
+ saves the right pointer a long trip back at block boundaries :: A constant-factor improvement.
- changes the answers :: Answers are identical.
- is required for correctness :: It is an optimisation.
- breaks the complexity :: It keeps it.