Offline queries and sorting

Why this matters when you build with AI

Ask an AI tool for "the number of distinct values in a range" and it will often write a set per query. The code is short and correct, and it is also O(n) per query. On a few hundred queries it looks fine. On a few hundred thousand queries it is too slow, and the tool will not mention that unless you ask for the limits.

The other common error is the opposite one. The tool sees that the queries could be answered in any order, so it reorders them, but it does not carry the answers back to the original order. The output then looks plausible and is in the wrong positions. The check that finds both errors is the same as before. Write a brute force that does the slow obvious thing, generate random small inputs, and compare the outputs query by query, in the original input order.

Every program below was compiled with g++ -O2 -std=c++17 -Wall -Wextra on the machine that wrote this lesson, which uses g++ 15.2.0. The random tests use a fixed seed. Nothing here was compared with an outside source. The claims are checked by the programs.

Online and offline

An online algorithm answers each query as soon as it arrives, before it sees the next one. A plain array with prefix sums is online: you can answer any range sum without knowing the other queries.

An offline algorithm reads all the queries first, then chooses the order in which to answer them. Offline is allowed here because the problem gives every query up front. The gain is that you can pick an order that makes the work easy. A sweep is the usual way to get that order: move one pointer across the array once, and answer each query when the pointer reaches the query's position.

The rule for the whole lesson is short. If all the input is available before you answer anything, you can sort the work. You still must return each answer to its original position.

The idea, with a worked example

Take the array a = [4, 1, 4, 2, 1, 4, 4, 9] and the query "how many distinct values are in [l, r)" for l = 1 and r = 5. The slice is [1, 4, 2, 1], which holds three distinct values: 1, 4 and 2.

Use the same half-open convention as the prefix sums lesson. The range [l, r) holds the indices l up to r - 1.

Now sweep the right end. Keep a flag at the last position of each value, and only the last position counts.

Add position 0, value 4. The flags are at position 0.
Add position 1, value 1. Flags at 0 and 1.
Add position 2, value 4. The value 4 already has a flag at 0, so that flag moves to 2. Flags at 1 and 2.
Add position 3, value 2. Flags at 1, 2 and 3.
The query [1, 5) is answered after the sweep has added positions 0 to 4. Add position 4, value 1. The old flag at 1 moves to 4. Flags at 2, 3 and 4.

The number of distinct values in [1, 5) is the number of flags between position 1 and position 4 inclusive. Those are the flags at 2, 3 and 4, so the count is 3. The answer is right, and only the last occurrence of each value needed a flag.

The flags live in a Fenwick tree. A Fenwick tree is an array that stores prefix sums and supports two operations in O(log n): add a value at one position, and get the sum of positions from 0 up to some index. Each step of the sweep does at most two point changes, and each query does two prefix sums.

Why sort by the right end? A sweep only moves forward. If queries were sorted by their left end, the flags for the earlier positions would have to be removed as the sweep passed them, and the bookkeeping would be harder. Sorting by r means the sweep only adds positions, and each query reads a range that ends at its own r.

The standard technique in C++

The core is a Fenwick tree, a compressed-value table for "last seen", and one pass over the queries sorted by r. The values are compressed to 0..k-1 so that the last occurrence of each value fits in a plain array. The function returns the answers in the original query order.

#include <bits/stdc++.h>
using namespace std;
 
// Fenwick tree over positions 0..n-1 (point add, prefix sum). Indices are 0-based in the API.
struct Fenwick {
    int n;
    vector<int> t;
    explicit Fenwick(int n) : n(n), t(n + 1, 0) {}
    void add(int i, int v) {
        for (i++; i <= n; i += i & -i) t[i] += v;
    }
    // Sum over positions 0..i. Returns 0 when i < 0.
    int prefix(int i) const {
        int s = 0;
        for (i++; i > 0; i -= i & -i) s += t[i];
        return s;
    }
};
 
// Offline distinct-count queries. Each query is a half-open range [l, r).
// Queries are sorted by r, so the sweep only moves forward.
vector<int> distinct_in_ranges(const vector<int> &a, const vector<pair<int, int>> &qs) {
    int n = (int)a.size();
    // Compress values to 0..k-1 so that "last seen" can be an array.
    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    vector<int> c(n);
    for (int i = 0; i < n; i++) c[i] = (int)(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());
 
    vector<int> order(qs.size());
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y) { return qs[x].second < qs[y].second; });
 
    // Invariant: the Fenwick tree has a 1 at position p exactly when p is the last occurrence
    // of its value among positions 0..next-1.
    vector<int> last(vals.size(), -1), ans(qs.size(), 0);
    Fenwick f(n);
    int next = 0;
    for (int idx : order) {
        auto [l, r] = qs[idx];
        while (next < r) {
            int v = c[next];
            if (last[v] >= 0) f.add(last[v], -1);  // this value's older occurrence no longer counts
            f.add(next, 1);
            last[v] = next;
            next++;
        }
        ans[idx] = f.prefix(r - 1) - f.prefix(l - 1);
    }
    return ans;
}

The main program reads the input, calls the function, and prints the answers in input order.

#include "distinct.h"
 
// Input: n q, then n values, then q lines "l r" (half-open range [l, r)).
// Output: for each query, the number of distinct values in a[l..r-1].
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    vector<pair<int, int>> qs(q);
    for (auto &[l, r] : qs) cin >> l >> r;
    vector<int> ans = distinct_in_ranges(a, qs);
    for (int x : ans) cout << x << "\n";
    return 0;
}

Two details matter here. The prefix function returns 0 for an index of -1, which lets a query with l = 0 use f.prefix(l - 1) with no special case. And the while loop adds each position exactly once, so the flags always reflect the array up to next - 1.

Worked original problem: the lantern colours

A row of n lanterns has a colour each. Colours are integers from 1 to 10^9. There are q questions. Each question gives a half-open range [l, r) and asks how many different colours appear among the lanterns in that range.

Input format. The first line has n and q. The second line has the n colours. Each of the next q lines has l and r. Limits: 1 <= n, q <= 2 * 10^5, and 0 <= l <= r <= n.

Sample input, which is the array from the worked example above, with five questions:

8 5
4 1 4 2 1 4 4 9
0 2
2 4
1 5
4 6
0 8

Work the first two by hand. The range [0, 2) holds 4 and 1, so the answer is 2. The range [2, 4) holds 4 and 2, so the answer is 2. The program prints the same two numbers, and it prints the rest in input order:

The last answer is 4 because the whole array holds the colours 4, 1, 2 and 9.

Checking against a brute force

The brute force makes a set for each range. A stress program makes random arrays with up to 15 values, drawn from a few small numbers (some multiplied by 7 so the values are not consecutive), and up to 30 random ranges per round, including empty ranges. It compares each answer with the brute force answer in input order.

all 3000 rounds passed, 46312 query checks

On a large random input with n = q = 2 * 10^5, the program ran in about 0.11 seconds of user time on the machine that wrote this lesson. That number depends on the machine, so treat it as an example.

Why the online version needs more machinery

The sweep works because it answers the queries in order of r. An online version must answer a query whose r is any value, in any order, and it has no sweep to lean on. The standard way to keep the same bookkeeping for every prefix at once is a persistent segment tree, which the persistence lesson covers. That structure keeps one version of the tree per prefix, and each query reads the version at its r. It costs O(log n) extra memory per update and more code. Mo's algorithm, from the Mo's lesson, is another option with a different cost. Choose by the limits: the sweep is the simplest of the three, and it needs all queries first.

Offline dynamic connectivity

The sweep works on one array with fixed values. A harder case is a graph where edges appear and disappear over time, and the question is "are u and v connected at this moment?"

Here is a small example with vertices 0 to 3 and no edges at the start. Operation 0 adds the edge 0 to 1. Operation 1 adds the edge 1 to 2. Operation 2 asks whether 0 and 2 are connected, and the answer is yes, through vertex 1. Operation 3 adds the edge 2 to 3. Operation 4 asks whether 0 and 3 are connected, and the answer is yes. Operation 5 removes the edge 1 to 2. Operation 6 asks about 0 and 3 again, and the answer is no, because the path ran through the removed edge.

A plain union-find cannot remove an edge. Its parent pointers lose the information about which union caused which merge. The offline trick avoids that. First read all the operations, then turn each edge into one time interval during which it exists. An edge added at time s and removed at time e exists during [s, e). An edge never removed exists until the end of the input.

Now each interval is a fact that is true for a stretch of time. Build a segment tree over the time axis. Put each interval into the O(log Q) nodes that cover it exactly, the same way a range update is stored in the lazy lesson. Then walk the time tree with depth-first search. When you enter a node, union the edges stored there. When you leave it, undo those unions. At a leaf, which is one moment in time, the union-find has exactly the edges alive at that moment, so a connectivity query is answered by two find calls.

Undoing a union needs a union-find that does not compress paths. A compressed path rewrites parent pointers that the undo cannot restore. The rollback union-find below uses union by size only, and it keeps a stack of the attachments it made.

#include <bits/stdc++.h>
using namespace std;
 
// Union-find with union by size and no path compression, so every merge can be undone.
struct RollbackDSU {
    vector<int> parent, size_of;
    vector<int> merged_child;  // stack of child roots that were attached; the parent is parent[child]
    explicit RollbackDSU(int n) : parent(n), size_of(n, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) const {
        while (parent[x] != x) x = parent[x];
        return x;
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;  // nothing to record: no change, nothing to undo
        if (size_of[a] < size_of[b]) swap(a, b);
        parent[b] = a;
        size_of[a] += size_of[b];
        merged_child.push_back(b);
        return true;
    }
    size_t checkpoint() const { return merged_child.size(); }
    void rollback(size_t to) {
        while (merged_child.size() > to) {
            int b = merged_child.back();
            merged_child.pop_back();
            int a = parent[b];
            size_of[a] -= size_of[b];
            parent[b] = b;
        }
    }
};
 
// Operations: type '+' adds edge (u, v), '-' removes one copy, '?' asks if u and v are connected.
struct Op {
    char type;
    int u, v;
};
 
// Offline dynamic connectivity by divide and conquer over time.
// Each edge copy is alive for the time interval [start, end) of operation indices.
// A segment tree over time stores each interval in O(log Q) nodes. A DFS over the tree
// adds the edges of a node with rollback union-find, and undoes them on the way back up.
struct DynConn {
    int n, Q;
    vector<Op> ops;
    vector<vector<pair<int, int>>> tree;
    vector<int> answer;  // answer[t] = 1 if connected, for '?' operations
    RollbackDSU dsu;
 
    DynConn(int n, const vector<Op> &ops)
        : n(n), Q((int)ops.size()), ops(ops), tree(4 * ops.size() + 4), answer(ops.size(), 0), dsu(n) {
        // Pair each '-' with the latest open '+' of the same edge (a stack per edge).
        map<pair<int, int>, vector<int>> open;
        for (int t = 0; t < Q; t++) {
            auto key = minmax(ops[t].u, ops[t].v);
            pair<int, int> k = {key.first, key.second};
            if (ops[t].type == '+') {
                open[k].push_back(t);
            } else if (ops[t].type == '-') {
                int s = open[k].back();
                open[k].pop_back();
                add_interval(1, 0, Q, s, t, k);
            }
        }
        for (auto &[k, starts] : open)
            for (int s : starts) add_interval(1, 0, Q, s, Q, k);
    }
 
    void add_interval(int node, int lo, int hi, int l, int r, pair<int, int> edge) {
        if (r <= lo || hi <= l) return;
        if (l <= lo && hi <= r) {
            tree[node].push_back(edge);
            return;
        }
        int mid = (lo + hi) / 2;
        add_interval(2 * node, lo, mid, l, r, edge);
        add_interval(2 * node + 1, mid, hi, l, r, edge);
    }
 
    void dfs(int node, int lo, int hi) {
        size_t snap = dsu.checkpoint();
        for (auto [u, v] : tree[node]) dsu.unite(u, v);
        if (hi - lo == 1) {
            if (ops[lo].type == '?') answer[lo] = dsu.find(ops[lo].u) == dsu.find(ops[lo].v);
        } else {
            int mid = (lo + hi) / 2;
            dfs(2 * node, lo, mid);
            dfs(2 * node + 1, mid, hi);
        }
        dsu.rollback(snap);
    }
 
    vector<int> solve() {
        if (Q > 0) dfs(1, 0, Q);
        return answer;
    }
};

The reader is short. It parses the operations and prints YES or NO for each question.

#include "dyn.h"
 
// Input: n Q, then Q lines: "+ u v", "- u v" or "? u v".
// Output: YES or NO for each "?" line, in order.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, Q;
    cin >> n >> Q;
    vector<Op> ops(Q);
    for (auto &op : ops) cin >> op.type >> op.u >> op.v;
    DynConn dc(n, ops);
    vector<int> ans = dc.solve();
    for (int t = 0; t < Q; t++)
        if (ops[t].type == '?') cout << (ans[t] ? "YES" : "NO") << "\n";
    return 0;
}

Sample input, which is the example above with one more question at the end:

The program prints:

YES
YES
NO
NO

Check the four questions by hand, in input order. ? 0 2 comes after the edges 0 to 1 and 1 to 2, so YES. ? 0 3 comes after the edge 2 to 3 is added, and the path 0, 1, 2, 3 exists, so YES. ? 0 3 comes after the edge 1 to 2 is removed, so the path is broken and the answer is NO. The last question ? 0 2 also comes after the removal, so NO.

The stress program builds random sequences of up to 40 operations on up to 7 vertices. It keeps the sequences valid by removing only edges that exist, and it allows duplicate edges. Each question is checked against a brute force that rebuilds a union-find from the current edge list.

all 3000 rounds passed, 25938 connectivity checks (15336 connected)

The bound for this method is O(Q log Q) intervals placed in the time tree, each union costing O(log n) in the worst case because union by size keeps the trees shallow. The total is O(Q log Q log n). This bound comes from the analysis above, not from a timing run in this lesson.

Complexity

The sweep for distinct counts costs O(n log n + q log q) for the sort, plus O((n + q) log n) for the Fenwick operations. The space is O(n + q).

The dynamic connectivity method costs O(Q log Q log n) in the worst case, with O(Q log Q) stored intervals. Rollback does not add a cost of its own, because each union is undone exactly once.

Common mistakes

Answering in sorted order and printing in that order. The sweep answers the queries sorted by r, so the results must go back to their input positions. Keep the original index with each query, as ans[idx] does in the code.
Leaving the old occurrence's flag in place. If the old flag stays, a value that appears twice in a range is counted twice. The fix is the f.add(last[v], -1) line, which must run before the new flag is set.
Using path compression in the rollback union-find. The undo cannot restore parent pointers that compression rewrote, so later rollbacks leave the structure wrong. Union by size and no compression is the rule for this method.
Forgetting that a removed edge leaves the interval open. An edge removed at time e must stop at e, not at the end of the input. The code uses t as the end of the interval, and that is the time of the removal.
Using the wrong key for an undirected edge. The edge 0 to 1 and the edge 1 to 0 are the same edge. The code stores the pair as (min, max), so a removal finds the matching addition.
Trusting an offline answer without the brute force. Offline code is easy to get subtly wrong because the order of the answers is not the input order. Compare every answer with a plain loop on random small inputs.

Checklist to keep

Before you choose the offline approach, check that all input is available before any answer is needed.
Sort the queries by the coordinate the sweep moves along, and keep each query's original index.
Use a Fenwick tree for point changes and prefix sums during a sweep.
Compress the values when a per-value array is needed.
Write the invariant as a comment: which positions hold a 1 at each step.
For dynamic connectivity, use union by size with no path compression, and undo each union when you leave a node.
Store each interval half-open, [start, end), so that removing an edge at time e stops exactly at e.
Compare every answer, in input order, with a brute force on random small inputs.

Practice problems

Each answer sits under the line "Show the answer".

Hand trace. Use the array a = [4, 1, 4, 2, 1, 4, 4, 9] and the query [4, 8). Find the distinct count by listing the values, then write the flags that the sweep holds after position 7 is added.

Show the answer

The values at indices 4 to 7 are 1, 4, 4 and 9, so the distinct count is 3. After the sweep adds position 7, the last occurrences are: value 4 at position 6, value 1 at position 4, value 2 at position 3, and value 9 at position 7. The flags are at positions 3, 4, 6 and 7. Between 4 and 7 inclusive, the flags are at 4, 6 and 7, which is 3.

Why sort by r? Explain in plain words why the sweep must sort the queries by their right end, not by their left end.

Show the answer

The sweep moves its pointer to the right and only adds positions. If it sorted by the left end, a query might need positions that the sweep has already passed, and the code would have to remove flags it had set. Sorting by r means each query is answered at the moment the pointer reaches its own right end, so every query reads the state it needs.

A rollback bug. Suppose someone adds path compression to the find function of RollbackDSU. Explain, in plain words, why a later rollback can leave the structure wrong, and give a small case where the parent of a vertex changes during a find.

Show the answer

Path compression sets the parent of each visited vertex to the root. Those parent changes are not recorded on the stack, so a rollback only undoes the recorded attachments. After the undo, a vertex may still point to a root that was attached later, which means find returns a root that is no longer correct. Concretely, if c points to b and b points to a, a find(c) with compression sets c to a. Undoing the union of b into a now leaves c attached to a, which is wrong. The fix is to keep union by size and skip the compression.

Read the intervals. For the dynamic sample, which has 8 operations numbered 0 to 7, give the interval [start, end) that the code stores for each of the edges 0 to 1, 1 to 2 and 2 to 3.

Show the answer

The edge 0 to 1 is added at operation 0 and never removed, so its interval is [0, 8). The edge 1 to 2 is added at operation 1 and removed at operation 5, so its interval is [1, 5). The edge 2 to 3 is added at operation 3 and never removed, so its interval is [3, 8). The question at operation 2 falls inside the first two intervals, which is why ? 0 2 is YES.

Explain the online gap. Suppose the queries of the distinct-count problem arrive one at a time and each answer must be given before the next query is read. Explain why the sweep no longer works, and name one structure from this course that can answer such queries and what it costs in memory.

Show the answer

The sweep needs all queries sorted by r before it starts, and an online query may ask for any r. A persistent segment tree stores one version of the Fenwick-style flags for each prefix, so a query can read the version at its own r. The cost is extra memory for every update, roughly O(log n) new nodes per position, and more code. The persistence lesson gives the details.

Exercise on your own machine

Do this in an empty folder, with g++ -O2 -std=c++17.

Save the Fenwick and distinct-count header as distinct.h, and the reader as solve_distinct.cpp. Compile and run it on the sample. You should see 2, 2, 3, 2 and 4.
Write stress_distinct.cpp that includes distinct.h, generates random arrays and ranges, and compares each answer with a set-based count. Run it with 3000 rounds.
Save the dynamic connectivity header as dyn.h and the reader as solve_dyn.cpp. Run it on the dynamic sample. You should see YES, YES, NO, NO.
Change the rollback union-find to use path compression, rebuild the stress test for the dynamic case, and see whether it still passes. Write down what changes in the output and why.

Your timings and any random values will differ from the lesson's numbers if you change the seed or the limits.

Summary

Offline methods read all queries first and choose an order that is easy to compute. For distinct counts, sorting by the right end and sweeping with a Fenwick tree gives each answer in logarithmic time. For edges that appear and disappear, placing each edge on a time segment tree and undoing unions with a rollback union-find answers each connectivity question at its moment. Either way, the answers must be returned to their input order, and both methods should be checked against a plain brute force.