Offline Query Processing & Mo's Algorithm

1. Introduction & Motivation

Most of the algorithms in this course are online: they must answer each query the instant it arrives, without knowing what will be asked next. A hash map lookup, a segment tree range sum, a binary search — all of these commit to an answer before the next question is even known.

But many real problems hand you the entire batch of queries up front: a competitive programming judge gives you $q$ range queries on an array before you output anything; a batch analytics job receives a full day's worth of range requests before it starts computing; a test harness lists every question it will ask before grading begins. When you are given all the queries in advance, you are not required to answer them in the order they were asked. You are free to reorder them into whatever sequence makes them cheapest to answer collectively — even though each individual query still asks about the same original, unreordered array.

This is the core idea of offline query processing: defer computation, look at the whole workload at once, sort it into a friendlier order, then sweep through it once. It sounds like a small trick, but it is one of the most powerful general techniques in algorithm design, because it turns a large family of "individually expensive, cannot be indexed online" problems into "cheap in aggregate." The flagship application of this idea for range queries on arrays is Mo's Algorithm, which this lesson builds toward after first establishing the general pattern with a simpler offline sweep.

2. Prerequisites

This lesson assumes comfort with arrays, sorting, and basic asymptotic notation. Two companion lessons supply ideas reused directly here:

• Square Root Decomposition introduces the block-size intuition — splitting an array or a query set into blocks of roughly $\sqrt{n}$ size to balance the cost of two different kinds of work. Mo's Algorithm reuses that exact intuition, but applies it to a set of queries rather than to the array's positions.
• Sorting Algorithms covers the comparison-sort machinery ($O(n\log n)$ sorting, custom comparators, stable ordering) that every offline technique in this lesson leans on to reorder its input before sweeping.

3. Sort-by-Threshold and Event Sorting

The simplest version of this pattern does not need blocks or square roots at all: sort by the array index itself. Consider the classic question, "for every position $i$, how many elements before position $i$ are strictly greater than $\text{arr}[i]$?" Answering this naively per index costs $O(n)$ per index and $O(n^2)$ overall. Offline processing fixes this by sweeping the array left to right exactly once while maintaining a running structure of "everything seen so far," answering each index's query the moment the sweep reaches it.

A frequency array works for small value ranges; a Fenwick tree (also called a Binary Indexed Tree, or BIT) makes the same sweep work for large or arbitrary value ranges in $O(\log n)$ per insert and per query, after compressing the values to ranks. The implementation below is self-contained — it builds its own small Fenwick tree inline, so you do not need to have studied Fenwick trees separately first. (Advanced Structures: Tries, Union-Find & Segment Trees covers Fenwick trees in more depth, if you want the general-purpose data structure afterward.)

def count_greater_before(arr):
    n = len(arr)
    sorted_vals = sorted(set(arr))
    rank = {v: i + 1 for i, v in enumerate(sorted_vals)}  # 1-indexed ranks
    size = len(sorted_vals)
    tree = [0] * (size + 1)

    def update(i, delta=1):
        while i <= size:
            tree[i] += delta
            i += i & (-i)

    def prefix_sum(i):
        total = 0
        while i > 0:
            total += tree[i]
            i -= i & (-i)
        return total

    answers = [0] * n
    inserted = 0
    for i in range(n):
        r = rank[arr[i]]
        count_le = prefix_sum(r)
        answers[i] = inserted - count_le
        update(r)
        inserted += 1
    return answers

arr = [5, 2, 6, 1]
print(count_greater_before(arr))  # [0, 1, 0, 3]

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

class FenwickTree {
public:
    explicit FenwickTree(int size) : tree_(size + 1, 0), size_(size) {}

    void update(int index, int delta = 1) {
        for (; index <= size_; index += index & (-index)) {
            tree_[index] += delta;
        }
    }

    int prefixSum(int index) const {
        int sum = 0;
        for (; index > 0; index -= index & (-index)) {
            sum += tree_[index];
        }
        return sum;
    }

private:
    std::vector<int> tree_;
    int size_;
};

std::vector<int> countGreaterBefore(const std::vector<int>& arr) {
    std::vector<int> sortedVals(arr.begin(), arr.end());
    std::sort(sortedVals.begin(), sortedVals.end());
    sortedVals.erase(std::unique(sortedVals.begin(), sortedVals.end()), sortedVals.end());

    auto rankOf = [&](int value) {
        return static_cast<int>(std::lower_bound(sortedVals.begin(), sortedVals.end(), value) - sortedVals.begin()) + 1;
    };

    FenwickTree tree(static_cast<int>(sortedVals.size()));
    std::vector<int> answers(arr.size());
    int inserted = 0;

    for (std::size_t i = 0; i < arr.size(); ++i) {
        int rank = rankOf(arr[i]);
        int countLessOrEqual = tree.prefixSum(rank);
        answers[i] = inserted - countLessOrEqual;
        tree.update(rank);
        ++inserted;
    }
    return answers;
}

int main() {
    std::vector<int> arr{5, 2, 6, 1};
    std::vector<int> answers = countGreaterBefore(arr);
    for (int a : answers) {
        std::cout << a << ' ';
    }
    std::cout << '\n';  // 0 1 0 3
}

import java.util.*;

public class OfflineCounting {
    static int[] tree;
    static int size;

    static void update(int index, int delta) {
        for (; index <= size; index += index & (-index)) {
            tree[index] += delta;
        }
    }

    static int prefixSum(int index) {
        int sum = 0;
        for (; index > 0; index -= index & (-index)) {
            sum += tree[index];
        }
        return sum;
    }

    static int[] countGreaterBefore(int[] arr) {
        int[] sortedVals = arr.clone();
        Arrays.sort(sortedVals);
        int uniqueCount = 0;
        for (int i = 0; i < sortedVals.length; i++) {
            if (i == 0 || sortedVals[i] != sortedVals[i - 1]) {
                sortedVals[uniqueCount++] = sortedVals[i];
            }
        }
        size = uniqueCount;
        tree = new int[size + 1];

        int[] answers = new int[arr.length];
        int inserted = 0;

        for (int i = 0; i < arr.length; i++) {
            int rank = Arrays.binarySearch(sortedVals, 0, uniqueCount, arr[i]) + 1;
            int countLessOrEqual = prefixSum(rank);
            answers[i] = inserted - countLessOrEqual;
            update(rank, 1);
            inserted++;
        }
        return answers;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 6, 1};
        System.out.println(Arrays.toString(countGreaterBefore(arr))); // [0, 1, 0, 3]
    }
}

4. Mo's Algorithm: Core Insight

Split the array's indices into blocks of size roughly $\sqrt{n}$. Sort the queries primarily by block(l) = l / block_size, and secondarily by r. Within a block, the left pointer only ever needs to move a total distance of $O(\sqrt{n})$ across all queries in that block (there are $O(\sqrt{n})$ blocks, giving $O(n\sqrt{n})$ left-pointer movement overall), while the right pointer moves monotonically forward within each block, for a total of $O(n)$ movement per block and $O(n\sqrt{n})$ across all blocks. Add movement when switching between blocks and the total across the whole batch is $O((n+q)\sqrt{n})$.

A common refinement is the odd-even trick: sort blocks with an even index by r ascending, and blocks with an odd index by r descending. Without this trick, the right pointer resets to a small value at the start of every new block and re-sweeps forward, wasting movement; alternating the sort direction lets the right pointer glide back down through the next block instead of jumping, which removes that reset cost and speeds up the sweep in practice, without changing the asymptotic bound.

5. A Concrete Example

6. Standard Mo's Algorithm Implementation

The implementation below reproduces the worked example exactly: it sorts queries by (block of l, then r with the odd-even alternating direction), then answers them with a sliding window whose add/remove callbacks track a frequency map and a running distinct count. The pointer-movement order matters: always grow both pointers outward first (adding elements), and only then shrink both pointers inward (removing elements). This order keeps the window valid at every intermediate step.

import math

def mo_distinct_queries(arr, queries):
    n = len(arr)
    block_size = max(1, int(math.sqrt(n)))

    indexed = list(enumerate(queries))  # (original_index, (l, r))

    def sort_key(item):
        _, (l, r) = item
        block = l // block_size
        if block % 2 == 0:
            return (block, r)
        return (block, -r)

    indexed.sort(key=sort_key)

    freq = {}
    distinct = 0

    def add(x):
        nonlocal distinct
        freq[x] = freq.get(x, 0) + 1
        if freq[x] == 1:
            distinct += 1

    def remove(x):
        nonlocal distinct
        freq[x] -= 1
        if freq[x] == 0:
            distinct -= 1

    answers = [0] * len(queries)
    cur_l, cur_r = 0, -1

    for original_index, (l, r) in indexed:
        while cur_r < r:
            cur_r += 1
            add(arr[cur_r])
        while cur_l > l:
            cur_l -= 1
            add(arr[cur_l])
        while cur_r > r:
            remove(arr[cur_r])
            cur_r -= 1
        while cur_l < l:
            remove(arr[cur_l])
            cur_l += 1
        answers[original_index] = distinct

    return answers

arr = [1, 2, 1, 3, 2]
queries = [(0, 2), (1, 4), (0, 4), (2, 3)]
print(mo_distinct_queries(arr, queries))  # [2, 3, 3, 2]

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

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

int main() {
    std::vector<int> arr{1, 2, 1, 3, 2};
    std::vector<std::pair<int, int>> raw{{0, 2}, {1, 4}, {0, 4}, {2, 3}};

    int n = static_cast<int>(arr.size());
    int blockSize = std::max(1, static_cast<int>(std::sqrt(n)));

    std::vector<Query> queries;
    for (int i = 0; i < static_cast<int>(raw.size()); ++i) {
        queries.push_back({raw[i].first, raw[i].second, i});
    }

    std::sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        int blockA = a.l / blockSize;
        int blockB = b.l / blockSize;
        if (blockA != blockB) {
            return blockA < blockB;
        }
        if (blockA % 2 == 0) {
            return a.r < b.r;
        }
        return a.r > b.r;
    });

    std::unordered_map<int, int> freq;
    int distinct = 0;

    auto add = [&](int x) {
        freq[x]++;
        if (freq[x] == 1) {
            distinct++;
        }
    };
    auto remove = [&](int x) {
        freq[x]--;
        if (freq[x] == 0) {
            distinct--;
        }
    };

    std::vector<int> answers(raw.size());
    int curL = 0, curR = -1;

    for (const auto& q : queries) {
        while (curR < q.r) {
            ++curR;
            add(arr[curR]);
        }
        while (curL > q.l) {
            --curL;
            add(arr[curL]);
        }
        while (curR > q.r) {
            remove(arr[curR]);
            --curR;
        }
        while (curL < q.l) {
            remove(arr[curL]);
            ++curL;
        }
        answers[q.index] = distinct;
    }

    for (int a : answers) {
        std::cout << a << ' ';
    }
    std::cout << '\n';  // 2 3 3 2
}

import java.util.*;

public class MoDistinctQueries {
    static int[] arr;
    static Map<Integer, Integer> freq = new HashMap<>();
    static int distinct = 0;

    static void add(int x) {
        freq.merge(x, 1, Integer::sum);
        if (freq.get(x) == 1) distinct++;
    }

    static void remove(int x) {
        int updated = freq.merge(x, -1, Integer::sum);
        if (updated == 0) distinct--;
    }

    public static void main(String[] args) {
        arr = new int[]{1, 2, 1, 3, 2};
        int[][] raw = {{0, 2}, {1, 4}, {0, 4}, {2, 3}};
        int n = arr.length;
        int blockSize = Math.max(1, (int) Math.sqrt(n));

        Integer[] order = new Integer[raw.length];
        for (int i = 0; i < raw.length; i++) order[i] = i;

        Arrays.sort(order, (a, b) -> {
            int blockA = raw[a][0] / blockSize;
            int blockB = raw[b][0] / blockSize;
            if (blockA != blockB) return Integer.compare(blockA, blockB);
            if (blockA % 2 == 0) return Integer.compare(raw[a][1], raw[b][1]);
            return Integer.compare(raw[b][1], raw[a][1]);
        });

        int[] answers = new int[raw.length];
        int curL = 0, curR = -1;

        for (int idx : order) {
            int l = raw[idx][0], r = raw[idx][1];
            while (curR < r) { curR++; add(arr[curR]); }
            while (curL > l) { curL--; add(arr[curL]); }
            while (curR > r) { remove(arr[curR]); curR--; }
            while (curL < l) { remove(arr[curL]); curL++; }
            answers[idx] = distinct;
        }

        System.out.println(Arrays.toString(answers)); // [2, 3, 3, 2]
    }
}

7. Mo's Algorithm with Modifications (Mo's with Updates)

The 3D extension

Standard Mo's Algorithm assumes the array never changes. Real problems often interleave range queries with point updates (arr[pos] = newValue). The extension adds a third dimension — time — representing how many updates have happened so far. Every query is recorded as a triple (l, r, t), where t is the count of updates that occurred strictly before that query in the original operation sequence. Queries are then sorted by (block(l), block(r), t), using a block size around $n^{2/3}$ instead of $\sqrt{n}$; this balances the three pointers (left, right, and time) and yields an overall complexity of $O(n^{5/3})$.

Answering a query now requires moving three pointers instead of two: the usual l/r window pointers, plus a t pointer that steps forward through recorded updates (applying them) or backward (undoing them) to bring the array to the state the query expects. An update only changes the answer if its position falls inside the current window: applying update (pos, oldVal, newVal) while pos is inside [curL, curR] means removing oldVal and adding newVal from the running frequency count; if pos is outside the window, the array value still changes, but the frequency count does not.

import math

def mo_with_updates(initial_arr, operations):
    """
    operations: list of tuples.
      ('Q', l, r)      -> range distinct-count query on the CURRENT array state
      ('U', pos, val)  -> point update: arr[pos] = val
    Returns a list of answers, one per 'Q' operation, in the original order.
    """
    arr = initial_arr[:]
    updates = []   # (pos, old_value, new_value) in original order
    queries = []   # (l, r, time, original_query_index)
    query_count = 0

    for op in operations:
        if op[0] == 'Q':
            _, l, r = op
            queries.append((l, r, len(updates), query_count))
            query_count += 1
        else:
            _, pos, val = op
            old_val = arr[pos]
            arr[pos] = val
            updates.append((pos, old_val, val))

    n = len(initial_arr)
    block_size = max(1, int(round(n ** (2 / 3))))

    def sort_key(q):
        l, r, t, _ = q
        return (l // block_size, r // block_size, t)

    queries.sort(key=sort_key)

    work_arr = initial_arr[:]
    freq = {}
    distinct = 0

    def add(x):
        nonlocal distinct
        freq[x] = freq.get(x, 0) + 1
        if freq[x] == 1:
            distinct += 1

    def remove(x):
        nonlocal distinct
        freq[x] -= 1
        if freq[x] == 0:
            distinct -= 1

    cur_l, cur_r, cur_t = 0, -1, 0
    answers = [0] * query_count

    for l, r, t, qi in queries:
        while cur_r < r:
            cur_r += 1
            add(work_arr[cur_r])
        while cur_l > l:
            cur_l -= 1
            add(work_arr[cur_l])
        while cur_r > r:
            remove(work_arr[cur_r])
            cur_r -= 1
        while cur_l < l:
            remove(work_arr[cur_l])
            cur_l += 1
        while cur_t < t:
            pos, _, new_val = updates[cur_t]
            if cur_l <= pos <= cur_r:
                remove(work_arr[pos])
                add(new_val)
            work_arr[pos] = new_val
            cur_t += 1
        while cur_t > t:
            cur_t -= 1
            pos, old_val, _ = updates[cur_t]
            if cur_l <= pos <= cur_r:
                remove(work_arr[pos])
                add(old_val)
            work_arr[pos] = old_val

        answers[qi] = distinct

    return answers

initial_arr = [1, 2, 3]
operations = [
    ('Q', 0, 2),
    ('U', 1, 5),
    ('Q', 0, 2),
    ('U', 0, 5),
    ('Q', 0, 1),
    ('Q', 0, 2),
]
print(mo_with_updates(initial_arr, operations))  # [3, 3, 1, 2]

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

struct Query { int l, r, t, index; };
struct Update { int pos, oldVal, newVal; };
struct Op { int type, a, b; };  // type 0 = query(l, r), type 1 = update(pos, val)

int main() {
    std::vector<int> initialArr{1, 2, 3};
    std::vector<Op> operations{
        {0, 0, 2},
        {1, 1, 5},
        {0, 0, 2},
        {1, 0, 5},
        {0, 0, 1},
        {0, 0, 2}
    };

    std::vector<int> arr = initialArr;
    std::vector<Update> updates;
    std::vector<Query> queries;
    int queryCount = 0;

    for (const auto& op : operations) {
        if (op.type == 0) {
            queries.push_back({op.a, op.b, static_cast<int>(updates.size()), queryCount});
            ++queryCount;
        } else {
            int pos = op.a, val = op.b;
            int oldVal = arr[pos];
            arr[pos] = val;
            updates.push_back({pos, oldVal, val});
        }
    }

    int n = static_cast<int>(initialArr.size());
    int blockSize = std::max(1, static_cast<int>(std::round(std::cbrt(static_cast<double>(n) * n))));

    std::sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        int blockLA = a.l / blockSize, blockLB = b.l / blockSize;
        if (blockLA != blockLB) return blockLA < blockLB;
        int blockRA = a.r / blockSize, blockRB = b.r / blockSize;
        if (blockRA != blockRB) return blockRA < blockRB;
        return a.t < b.t;
    });

    std::vector<int> workArr = initialArr;
    std::unordered_map<int, int> freq;
    int distinct = 0;

    auto add = [&](int x) {
        freq[x]++;
        if (freq[x] == 1) distinct++;
    };
    auto remove = [&](int x) {
        freq[x]--;
        if (freq[x] == 0) distinct--;
    };

    int curL = 0, curR = -1, curT = 0;
    std::vector<int> answers(queryCount);

    for (const auto& q : queries) {
        while (curR < q.r) { ++curR; add(workArr[curR]); }
        while (curL > q.l) { --curL; add(workArr[curL]); }
        while (curR > q.r) { remove(workArr[curR]); --curR; }
        while (curL < q.l) { remove(workArr[curL]); ++curL; }
        while (curT < q.t) {
            const auto& u = updates[curT];
            if (u.pos >= curL && u.pos <= curR) {
                remove(workArr[u.pos]);
                add(u.newVal);
            }
            workArr[u.pos] = u.newVal;
            ++curT;
        }
        while (curT > q.t) {
            --curT;
            const auto& u = updates[curT];
            if (u.pos >= curL && u.pos <= curR) {
                remove(workArr[u.pos]);
                add(u.oldVal);
            }
            workArr[u.pos] = u.oldVal;
        }
        answers[q.index] = distinct;
    }

    for (int a : answers) std::cout << a << ' ';
    std::cout << '\n';  // 3 3 1 2
}

import java.util.*;

public class MoWithUpdates {
    static class Query {
        int l, r, t, index;
        Query(int l, int r, int t, int index) { this.l = l; this.r = r; this.t = t; this.index = index; }
    }
    static class Update {
        int pos, oldVal, newVal;
        Update(int pos, int oldVal, int newVal) { this.pos = pos; this.oldVal = oldVal; this.newVal = newVal; }
    }

    static Map<Integer, Integer> freq = new HashMap<>();
    static int distinct = 0;

    static void add(int x) {
        freq.merge(x, 1, Integer::sum);
        if (freq.get(x) == 1) distinct++;
    }

    static void remove(int x) {
        int updated = freq.merge(x, -1, Integer::sum);
        if (updated == 0) distinct--;
    }

    public static void main(String[] args) {
        int[] initialArr = {1, 2, 3};
        // operations: type 0 = query(l, r), type 1 = update(pos, val)
        int[][] operations = {
            {0, 0, 2},
            {1, 1, 5},
            {0, 0, 2},
            {1, 0, 5},
            {0, 0, 1},
            {0, 0, 2}
        };

        int[] arr = initialArr.clone();
        List<Update> updates = new ArrayList<>();
        List<Query> queries = new ArrayList<>();
        int queryCount = 0;

        for (int[] op : operations) {
            if (op[0] == 0) {
                queries.add(new Query(op[1], op[2], updates.size(), queryCount));
                queryCount++;
            } else {
                int pos = op[1], val = op[2];
                int oldVal = arr[pos];
                arr[pos] = val;
                updates.add(new Update(pos, oldVal, val));
            }
        }

        int n = initialArr.length;
        int blockSize = Math.max(1, (int) Math.round(Math.cbrt((double) n * n)));

        queries.sort((a, b) -> {
            int blockLA = a.l / blockSize, blockLB = b.l / blockSize;
            if (blockLA != blockLB) return Integer.compare(blockLA, blockLB);
            int blockRA = a.r / blockSize, blockRB = b.r / blockSize;
            if (blockRA != blockRB) return Integer.compare(blockRA, blockRB);
            return Integer.compare(a.t, b.t);
        });

        int[] workArr = initialArr.clone();
        int curL = 0, curR = -1, curT = 0;
        int[] answers = new int[queryCount];

        for (Query q : queries) {
            while (curR < q.r) { curR++; add(workArr[curR]); }
            while (curL > q.l) { curL--; add(workArr[curL]); }
            while (curR > q.r) { remove(workArr[curR]); curR--; }
            while (curL < q.l) { remove(workArr[curL]); curL++; }
            while (curT < q.t) {
                Update u = updates.get(curT);
                if (u.pos >= curL && u.pos <= curR) {
                    remove(workArr[u.pos]);
                    add(u.newVal);
                }
                workArr[u.pos] = u.newVal;
                curT++;
            }
            while (curT > q.t) {
                curT--;
                Update u = updates.get(curT);
                if (u.pos >= curL && u.pos <= curR) {
                    remove(workArr[u.pos]);
                    add(u.oldVal);
                }
                workArr[u.pos] = u.oldVal;
            }
            answers[q.index] = distinct;
        }

        System.out.println(Arrays.toString(answers)); // [3, 3, 1, 2]
    }
}

8. Hilbert-Order Optimization

Sorting by (block, alternating r) is not the only ordering that bounds pointer movement by $O((n+q)\sqrt{n})$. A popular alternative in competitive programming maps each query (l, r) to a point on a Hilbert space-filling curve and sorts queries by their position along that curve instead. The Hilbert curve visits every cell of a grid exactly once while guaranteeing that points close together along the curve are also close together in the 2D grid; sorting by a single "Hilbert index" number therefore keeps consecutive queries close in both l and r simultaneously, without needing the odd-even direction-flipping trick or careful block-boundary tie-breaking.

The fundamental algorithm does not change at all — the same add/remove sliding window from the previous sections still answers the sorted queries. Only the sort key changes, from a (block, r) pair to a single Hilbert-curve index:

def hilbert_index(x, y, order):
    """Map point (x, y) on a 2**order x 2**order grid to its 1D Hilbert-curve index."""
    d = 0
    s = 1 << (order - 1)
    while s > 0:
        rx = 1 if (x & s) > 0 else 0
        ry = 1 if (y & s) > 0 else 0
        d += s * s * ((3 * rx) ^ ry)
        if ry == 0:
            if rx == 1:
                x = s - 1 - x
                y = s - 1 - y
            x, y = y, x
        s >>= 1
    return d

# sort queries by their Hilbert index instead of (block, direction):
# queries.sort(key=lambda q: hilbert_index(q.l, q.r, order))

In practice, Hilbert order tends to produce noticeably better cache locality and a lower constant factor than the block-and-direction ordering, because the curve avoids the sharp jumps that can occur at block boundaries. The asymptotic bound is the same class of result, but the tighter practical behavior is why competitive programmers reach for it once Mo's Algorithm becomes a performance bottleneck.

9. Complexity Analysis

That last comparison is the reason Mo's Algorithm exists at all. Some aggregate operations, such as "count of distinct elements in [l, r]," do not have an efficient online segment-tree or Fenwick-tree solution, because they are not decomposable: knowing the distinct count of the left half and the distinct count of the right half of a range does not tell you the distinct count of the combined range (an element could appear in both halves, or in neither, and you cannot tell which from the two half-answers alone). Range sum, range min, and range max are decomposable — you can merge two sub-answers in $O(1)$ — which is exactly why segment trees and Fenwick trees handle them online. Range-distinct-count, by contrast, has no known $O(\log n)$-per-query online data structure for arbitrary updates and arbitrary ranges. Mo's Algorithm sidesteps the decomposability requirement entirely by never merging sub-answers: it only ever adds or removes one element from a running answer, which works for any operation that supports incremental add/remove, decomposable or not. That is why an offline, sqrt-decomposition-based sweep is sometimes the only practical polynomial-time approach for a given aggregate.

10. Applications & Alternatives

When an online structure for the exact operation exists — range sum, range minimum, range XOR, and other decomposable aggregates — prefer it: a Fenwick tree or segment tree answers each query as it arrives, supports true online use (queries interleaved with updates in real time), and needs no upfront knowledge of future queries. Reach for Mo's Algorithm specifically when the aggregate cannot be merged in $O(1)$ across sub-ranges, or when a segment-tree-based structure exists in theory but is significantly harder to implement correctly than a sliding add/remove window.

11. Exercises & Mastery

Easy

1. Given an array and a batch of offline range-sum queries, explain why plain prefix sums already solve this in $O(1)$ per query after $O(n)$ preprocessing, and why Mo's Algorithm's $O((n+q)\sqrt{n})$ sliding window is unnecessary overhead here. (See Prefix Sums & Difference Arrays for the prefix-sum construction itself — this exercise only asks you to recognize when it suffices, not to re-derive it.)
2. Trace the offline-counting sweep from Section 3 on arr = [3, 1, 2] and confirm the per-index answers by hand.

Medium

1. Extend the worked example from Section 5 to arr = [2, 1, 2, 3, 1, 3] with queries [0,3], [1,5], [2,4], [0,5]. Compute the block assignments, the sorted processing order, and each answer using the standard Mo's Algorithm implementation from Section 6.
2. Modify the Section 6 implementation to answer "sum of distinct values in the range" instead of "count of distinct values," changing only the add/remove callbacks.

Hard

1. Using the Mo's-with-updates implementation from Section 7, trace initial_arr = [4, 4, 2] with operations [('Q',0,2), ('U',2,4), ('Q',0,2), ('U',0,1), ('Q',0,1), ('Q',0,2)] by hand, tracking the window, the time pointer, and the frequency map at each step.
2. Derive why the optimal block size for Mo's Algorithm with updates is $\Theta(n^{2/3})$ rather than $\Theta(\sqrt{n})$, by writing the total cost as a function of block size and minimizing it.

Review rhythm: tomorrow, re-derive the pointer-movement bound $O((n+q)\sqrt{n})$ without looking at this lesson; next week, implement standard Mo's Algorithm from a blank file in all three languages; several weeks later, recognize the same "sort the queries, sweep once" pattern in a new offline problem outside range queries entirely. Finally, teach someone the difference between a decomposable aggregate (fits a segment tree) and one that only supports incremental add/remove (needs Mo's Algorithm).

12. Summary Cheat Sheet

• Offline processing means you have every query in advance and are free to reorder them before answering any of them.
• Sort-and-sweep (Section 3) answers a batch of "as of position $i$" queries in one left-to-right pass using a Fenwick tree, and solves inversion counting as a special case.
• Mo's Algorithm sorts range queries by (block of $l$, then $r$, alternating direction per block) and answers them with a sliding [l, r] window that only ever adds or removes one element at a time.
• Always grow both pointers outward (adding) before shrinking either pointer inward (removing) to keep the window valid mid-transition.
• Standard Mo's Algorithm: $O((n+q)\sqrt{n})$ time. Mo's Algorithm with updates: $O(n^{5/3})$ time using a block size around $n^{2/3}$ and a third "time" pointer.
• Hilbert-curve ordering is a drop-in replacement sort key that improves practical cache locality without changing the fundamental sliding-window algorithm.
• Reach for Mo's Algorithm specifically when the aggregate you need is not decomposable across sub-ranges, so no online segment-tree or Fenwick-tree solution exists.