Offline Query Processing, in depth: reorder the queries, sweep once, and turn hard online problems into Fenwick and union-find exercises

The offline contract

Write the contract down before choosing a technique, because every bug in this family is a broken contract. An offline solution may assume three things. First, all queries are known before the first answer is due. Second, no query depends on the answer to an earlier one. Third, the data the queries run against is either fixed or changes by a list of updates that is also known in advance.

If all three hold, the queries are a set, not a sequence, and you can process the set in whatever order makes the data structure's job easiest. The original order only matters at the very end, when you write each answer to the slot of the query that asked it. That is why every implementation below starts by tagging each query with its index and ends by writing ans[i] rather than appending to a list. BIT and DSU in the snippets are a standard Fenwick tree and union-find.

The gain usually comes from monotonicity. Online, a query about the range [l, r] or the graph "using edges up to weight w" needs a structure that can represent every possible prefix at once, which is what persistent structures do. Offline, you visit the prefixes in increasing order and keep one mutable structure that only ever grows. Growing is cheap; versioning is not.

Sort by right endpoint: distinct values in a range

The classic first example: given an array and many queries (l, r), report how many distinct values appear in a[l..r]. Online, this needs a persistent segment tree or a merge-sort tree. Offline, sort the queries by r and sweep r from left to right. Keep a Fenwick tree over positions where position j holds 1 if j is the last occurrence of a[j] seen so far, and 0 otherwise. When the sweep reaches position r with value v, clear the bit at v's previous last occurrence and set the bit at r. Now every value that appears in [l, r] contributes exactly one 1 inside [l, r], at its rightmost occurrence, so the answer is a range sum.

def distinct_offline(arr, queries):
    order = sorted(range(len(queries)), key=lambda q: queries[q][1])
    bit = BIT(len(arr)); last = {}; ans = [0] * len(queries); r = -1
    for qi in order:
        l, rq = queries[qi]
        while r < rq:                      # extend the sweep to this query's r
            r += 1
            v = arr[r]
            if v in last:
                bit.add(last[v], -1)       # old last occurrence no longer counts
            bit.add(r, +1); last[v] = r
        ans[qi] = bit.range(l, rq)         # write by original index
    return ans

Worked example with arr = [1, 2, 1, 3, 2] and queries (1,4), (0,2), (2,3), (0,4). Sorted by r, the order is (0,2), (2,3), then the two queries ending at 4. After the sweep reaches r = 2, the marked positions are 1 (the 2) and 2 (the second 1); position 0 was cleared. The sum over [0, 2] is 2. At r = 3, position 3 is set, and [2, 3] sums to 2. At r = 4 the second 2 moves the mark from position 1 to 4, leaving marks at 2, 3 and 4, so [1, 4] and [0, 4] both give 3. Running the code returns [3, 2, 2, 3] in the original order. Total cost is O((n + m) log n) plus the sort. The Fenwick tree itself is covered in the Fenwick tree deep dive.

Sort by threshold: offline Kruskal queries

The second family sorts by a threshold. Typical question: for each query (v, w), how many vertices can v reach using only edges of weight at most w? Online, you would need a Kruskal reconstruction tree or a persistent union-find. Offline, sort edges by weight and queries by w, then run Kruskal's loop and pause it at each query's threshold. The union-find only ever merges, which is exactly what it is good at.

def reachable_under(n, edges, queries):           # edges: (u, v, weight)
    edges = sorted(edges, key=lambda e: e[2])
    order = sorted(range(len(queries)), key=lambda q: queries[q][1])
    d = DSU(n); ans = [0] * len(queries); i = 0
    for qi in order:
        v, w = queries[qi]
        while i < len(edges) and edges[i][2] <= w:  # admit every edge allowed by w
            d.union(edges[i][0], edges[i][1]); i += 1
        ans[qi] = d.sz[d.find(v)]                     # component size
    return ans

With five vertices, edges (0-1, 4), (1-2, 2), (2-3, 7), (3-4, 1), (0-4, 9) and queries (0, 5), (3, 1), (2, 7), (0, 3), the code returns [3, 2, 5, 1]. Query (0, 3) sees only the edges of weight 1 and 2, which do not touch vertex 0, so the answer is 1. Query (0, 5) adds the weight-4 edge, joining 0 to {1, 2}. Note the <=: whether a query's threshold is inclusive decides whether edges are admitted before or after a tie, and getting it wrong passes every test without ties. Union by size and path compression are explained in union-find in depth.

Reverse time: deletions become unions

Union-find cannot delete. But if every deletion is known in advance, run time backwards. Start from the final graph (all edges minus every edge that is ever deleted), walk the operations in reverse, and treat each deletion as an insertion. Queries are answered in the reversed sweep and the answer list is reversed at the end.

def deletions_reversed(n, edges, ops):            # ops: ("del", k) or ("ask", u, v)
    deleted = {o[1] for o in ops if o[0] == "del"}
    d = DSU(n)
    for k, (u, v) in enumerate(edges):
        if k not in deleted:
            d.union(u, v)                          # the graph after every deletion
    out = []
    for o in reversed(ops):
        if o[0] == "ask":
            out.append(d.find(o[1]) == d.find(o[2]))
        else:
            d.union(*edges[o[1]])                  # un-delete = insert
    return out[::-1]

On a four-cycle 0-1-2-3-0 with a chord 1-3, the operations ask(0,2), del(1-2), del(1-3), ask(1,2), del(2-3), ask(2,3), ask(0,3) give [True, True, False, True]. After the first two deletions, 1 still reaches 2 through 0 and 3. After 2-3 goes, vertex 2 is isolated. This version assumes each edge is deleted at most once and never re-added. When edges come and go repeatedly, each edge has several lifetime intervals, and the right tool is a segment tree over time with a rollback union-find, covered in offline dynamic connectivity in depth.

Parallel binary search

Some queries ask "when": for each pair (u, v), what is the earliest update after which u and v are connected? One query alone is a binary search over time, replaying the updates for each probe, so m queries cost O(m T log T) union operations. Parallel binary search keeps a [lo, hi] interval per query and runs all the searches together. In each round, bucket every unfinished query by its midpoint, replay the T updates once, and check each bucket when the replay reaches its midpoint. After about log T rounds every interval has collapsed, for a total of O((T + m) log T) operations.

def parallel_binary_search(n, updates, targets):
    T, q = len(updates), len(targets)
    lo, hi = [0] * q, [T] * q                     # hi == T means "never"
    while any(lo[i] < hi[i] for i in range(q)):
        buckets = {}
        for i in range(q):
            if lo[i] < hi[i]:
                buckets.setdefault((lo[i] + hi[i]) // 2, []).append(i)
        d = DSU(n)                                 # fresh replay each round
        for t in range(T):
            d.union(*updates[t])
            for i in buckets.get(t, []):
                u, v = targets[i]
                if d.find(u) == d.find(v): hi[i] = t
                else:                      lo[i] = t + 1
    return [x if x < T else -1 for x in lo]

With eight vertices, updates 0-1, 2-3, 1-2, 4-5, 3-4, 5-6 at times 0 to 5, and targets (0,3), (4,5), (0,6), (0,7), the result is [2, 3, 5, -1] after 3 rounds. The predicate must be monotone in time: once true, it stays true. Connectivity under insertions is monotone; anything with deletions is not, and the search silently returns wrong answers if you use it there.

CDQ divide and conquer, Mo's algorithm and a selection table

Two more tools finish the kit. Mo's algorithm sorts range queries into blocks so that a window with cheap add and remove operations moves O((n + m) √n) steps in total. It applies when the answer for [l, r] can be updated by one element at either end, such as a mode or a count of pairs. CDQ divide and conquer handles a mix of updates and queries over time: split the timeline in half, solve each half recursively, then account for the left half's updates on the right half's queries with a single sweep. It turns a dynamic problem into a static one at a cost of one extra log factor, and is the standard way to do 3D dominance counting offline.

When you are not allowed to go offline

Check that you are allowed to go offline before choosing any of these. Contest problems that want to rule it out encode each query with the previous answer, for example l = l' XOR last_answer. You cannot decode query k until you have answered query k-1, so you cannot sort.

When offline is forbidden, the fallback is to build the version history the sweep would have walked through: a persistent Fenwick or segment tree indexed by r, a Kruskal reconstruction tree for thresholds, or a fully dynamic connectivity structure. These are correct but heavier, in memory and in code. Persistent structures and their costs are in persistent data structures in depth.

The same idea in batch systems

The same move runs inside batch data systems. A point-in-time feature join asks, for every training example, the value each feature had at that example's timestamp. Done online, that is one lookup per example against a versioned store. Done offline, you sort examples and feature updates by timestamp and merge the two streams in one pass, which is the sort-by-key sweep with timestamps as the key. Feature store architecture explains why getting that join wrong leaks future data into training.

Evaluation jobs are another case: scoring a checkpoint at every decision threshold is one sort and one sweep instead of m passes.

Failure modes

• Answers come out in sweep order. Appending answers instead of writing ans[i] passes any test whose queries happen to be sorted already. Always carry the original index.
• Inclusive versus exclusive keys. A threshold query that means "weight below w" needs <, not <=. Ties expose it; add a test where an edge weight equals a query threshold.
• Hidden online dependency. A query encoded with the previous answer, or a service whose next request depends on the last response, cannot be reordered. Sorting it produces fluent wrong output.
• Non-monotone predicate under parallel binary search. If the property can become false again, the search converges to an arbitrary boundary. Prove monotonicity before you code.
• Reversed deletions with re-insertion. The reverse trick assumes each edge dies once. A second lifetime needs the segment tree over time.
• Memory. Offline means holding every query at once. For billions of queries, sort in chunks or push the sort into the engine that stores them.

Trade-offs

Offline processing buys simpler, faster structures with latency. You cannot answer the first query until you have read the last one, so it fits batch jobs, nightly analytics and contest input files, not request-response services. The code is usually shorter than the online alternative, but the correctness argument moves into the ordering: sort keys, tie-breaking and index restoration are where the bugs hide.

What to do next

1. Write down whether your queries are independent and known up front. If either is false, stop and pick an online structure.
2. Find the monotone key: right endpoint, threshold, reversed time or candidate answer.
3. Tag every query with its index and write answers by index, never by position in the sweep.
4. Implement the sweep, then a brute-force checker, and compare on a few thousand small random inputs that include ties.
5. For "earliest time" questions, prove the predicate is monotone before using parallel binary search.
6. If the answer needs add and remove at both ends of a window, move to Mo's algorithm; if updates and queries interleave, try CDQ divide and conquer.