iii. Offline Techniques

If all queries are known in advance, you can reorder them, reverse time, batch them, or split time into a tree. A simpler structure then suffices. Forced-online problems (parameters XORed with the last answer) exist precisely to block these tricks.

Decision list

Situation	Technique
queries on ranges with a value threshold	sweep by value with a BIT over positions
queries $[l, r]$ answerable by maintaining something as $r$ grows	sweep $r$ , structure indexed by $l$ (“last occurrence” trick)
only deletions (DSU, sets that can’t delete)	reverse time: deletions become insertions
additions and deletions, structure supports undo	segment tree over time + rollback
a window of updates (oldest removed, newest added), structure supports undo	queue undo trick
the answer for each query is a monotone event time	parallel binary search
incremental add/remove of single elements is cheap	Mo’s algorithm
update/query interactions with 2-3 static conditions	CDQ
only insertions, static structure with decomposable queries	binary grouping (static-to-dynamic)
many queries, few distinct “shapes”	group queries by key, answer each group once
LCA queries on a static tree	Tarjan’s offline LCA: DFS order + DSU, $O ((n + q) α)$

Sweeping

Sweep by value. “Count elements $\leq x$ in $[l, r]$ ”: sort elements by value and queries by $x$ ; insert positions into a BIT as $x$ grows. $O ((n + q) lo g n)$ , $O (n)$ memory, which beats a merge sort tree on both counts.

Proof: the value-sweep answers each query correctly

Process elements and queries together in increasing order of value, breaking ties so every element with value $\leq x$ is inserted before query $x$ is answered (e.g. insert all elements of value $v$ before answering queries with threshold $v$ ). At the moment query $(l, r, x)$ is answered, the BIT contains exactly the positions of elements with value $\leq x$ inserted so far — which, by the tie-breaking rule, is exactly the set of elements with value $\leq x$ in the whole array, since nothing with value $> x$ has been inserted yet and everything with value $\leq x$ has. The BIT range-sum over $[l, r]$ then counts exactly the elements in $[l, r]$ with value $\leq x$ . Each element is inserted once ( $O (lo g n)$ ) and each query answered once ( $O (lo g n)$ ), giving $O ((n + q) lo g n)$ total. $■$

Sweep by right end with last occurrences. “Number of distinct values in $[l, r]$ ”: sweep $r$ ; keep a 1 at the last occurrence of each value seen so far. The answer is the BIT sum over $[l, r]$ . The same scheme answers:

Proof: the last-occurrence BIT sum equals the distinct count

Sort queries by $r$ and sweep $r$ from $1$ to $n$ ; whenever a value $v = a_{r}$ is seen, clear its old mark (at its previous occurrence, if any) and set a new mark at position $r$ . Invariant after processing position $r$ : the BIT has exactly one marked position per distinct value appearing in $a [1.. r]$ , namely that value’s last (rightmost) occurrence so far. At the moment a query $(l, r)$ is answered (with the sweep exactly at $r$ ), the marked positions in $[1, r]$ are exactly the rightmost occurrences of the distinct values in $a [1.. r]$ — one mark per distinct value, by the invariant, and no value has two marks since each new occurrence clears the previous one. Restricting the BIT sum to $[l, r]$ keeps exactly the values whose mark (rightmost occurrence in $a [1.. r]$ ) falls in $[l, r]$ . A value appears in $a [l .. r]$ iff its rightmost occurrence within $[1, r]$ is $\geq l$ : if it occurs anywhere in $[l, r]$ , its rightmost occurrence overall is at least that position, so $\geq l$ ; conversely if its rightmost occurrence is $\geq l$ and (by the sweep) $\leq r$ , that occurrence itself lies in $[l, r]$ . So the marks landing in $[l, r]$ are exactly the distinct values of $a [l .. r]$ , one mark each. $■$

sum of distinct values in a range;
“does the range have a duplicate” (the max over $[l, r]$ of previous-occurrence must be $\geq l$ );
minimum distance between equal values in a range (sweep $r$ , point-update at $prev (r)$ with $r - prev (r)$ , range min over $[l, r]$ );
mex of a range (segment tree over values storing last occurrence, find the first value with last occurrence $< l$ ).

Sweep with “latest/earliest event” per position handles “after which update does position $i$ first become $\geq x$ ” style questions combined with parallel binary search.

Reversing time

Union-find can’t delete, but a deletion run backwards is a union. Apply all deletions first (the final state), then walk the operations backwards, re-adding and answering. Applies to: edge removals with connectivity or component-size queries, “remove cells from a grid and count islands”, deleting elements from a set where you need predecessor/successor via DSU “next pointer”.

Proof: reversed deletions behave as unions

Let $S_{0} \supseteq S_{1} \supseteq \dots \supseteq S_{m}$ be the sequence of states, where $S_{t}$ is obtained from $S_{t - 1}$ by deleting one element (an edge, a grid cell, a set element). A query asked “between deletion $t$ and $t + 1$ ” needs the structure in state $S_{t}$ . Walking backwards from $S_{m}$ (the final, fully-deleted state, built directly) to $S_{0}$ , going from $S_{t}$ to $S_{t - 1}$ means adding back exactly the element deleted at step $t$ — which is a pure insertion/union, never a removal, since $S_{t - 1} = S_{t} \cup {deleted element at step t}$ by definition of the forward process. So the reversed walk visits every state $S_{m}, S_{m - 1}, \dots, S_{0}$ using only insertions, letting a union-only structure (DSU) answer every query by answering it when the reversed walk reaches the matching state, then reporting results back to the user in original time order. $■$

Segment tree over time (offline deletion)

Each element exists during an interval of time $[t_{1}, t_{2})$ . Insert it into the $O (lo g q)$ segment-tree nodes covering that interval. DFS the tree: on entering a node apply its elements, at a leaf answer the query, on leaving undo them. Requires only apply + undo last (rollback DSU, DSU with parity, XOR basis with a history stack, a knapsack DP layer stack).

Total cost: $O (q lo g q)$ applications times the apply cost. Rollback DSU uses union by size without path compression, so each find is $O (lo g n)$ . Details: Dynamic Connectivity.

Proof: $O (q lo g q)$ total applications

A segment tree over $q$ leaves decomposes any range $[t_{1}, t_{2})$ into at most $O (lo g q)$ disjoint canonical nodes (the standard range-update decomposition: at each of the $O (lo g q)$ depths, at most two nodes of the decomposition touch that depth, one from the left boundary and one from the right, so the count is linear in depth, i.e. $O (lo g q)$ overall). Each of the up to $n$ elements with a bounded lifetime is inserted into $O (lo g q)$ nodes, so the total number of (element, node) insertions is $O (n lo g q) = O (q lo g q)$ when $n = O (q)$ . The DFS applies each node’s stored elements exactly once on entry and undoes them exactly once on exit, so the total number of apply/undo calls equals the total number of insertions, $O (q lo g q)$ . $■$

Queue undo trick

Turns a structure with apply / undo the last apply (a stack) into one that can also remove the oldest update (a queue), at $O (lo g n)$ amortized applies per operation. Typical use: two pointers over edges where the window must stay bipartite or acyclic (CF 1386C “Joker”).

The stack holds two kinds of updates: A (scheduled to be popped soon, oldest first) and B (pushed normally). To pop the oldest: if no A remains, undo everything and re-push it all as A in reverse order. Otherwise undo from the top until as many A’s as B’s have been removed (or the B’s are exhausted), then re-push the B’s and then the A’s so the A’s are on top, and finally undo the oldest A. Each update is re-applied $O (lo g n)$ times amortized.

Proof: $O (lo g n)$ amortized re-applications per update

Give every update a rank: each time it is popped and re-pushed as part of a reshuffle (the “undo until as many A’s as B’s” step, or the full-flip step), its rank increases by exactly 1. The reshuffle step stops as soon as the number of popped B’s reaches the number of popped A’s (or the A-region is exhausted), so a reshuffle that increases some update’s rank from $k$ to $k + 1$ always pairs it with at least as many freshly pushed (rank-0-since-last-reshuffle) updates as there are rank- $k$ updates being promoted. Charging each promotion to the newly-pushed updates it consumes, an update cannot be promoted to rank $k + 1$ until at least as many new pushes have occurred as the number of rank- $\geq k$ updates currently alive — the same “amount of fresh work needed to justify a promotion at least matches the batch being promoted” structure as a binary counter’s carry chain or small-to-large merging. Since the total number of live updates is at most $n$ , no update can reach rank higher than $lo g_{2} n$ (each rank level needs the surviving batch to have been matched by at least its own size in fresh pushes, so the batch at rank $k$ has “cost” $\geq 2^{k}$ pushes behind it, bounded by $n$ ). Summing ranks over all updates — which equals the total number of re-applications — gives $O (n lo g n)$ over $n$ operations, i.e. $O (lo g n)$ amortized per update. $■$

template<class DS, class Upd> struct QueueUndo {
    DS ds; vector<pair<Upd, bool>> st; int bottom = 0;     // bool: is A
    void push(const Upd& u, bool a = false) { ds.apply(u); st.push_back({u, a}); }
    void pop() {
        while (bottom < sz(st) && !st[bottom].second) bottom++;
        if (bottom == sz(st)) {                            // no A left: flip everything to A
            vector<Upd> all;
            while (!st.empty()) all.push_back(st.back().first), st.pop_back(), ds.undo();
            for (auto& u : all) push(u, true);
            bottom = 0;
        }
        vector<Upd> t[2];
        do { t[st.back().second].push_back(st.back().first); st.pop_back(); ds.undo(); }
        while (t[1].size() < t[0].size() && sz(st) > bottom);
        for (int i : {0, 1}) { reverse(all(t[i])); for (auto& u : t[i]) push(u, i); }
        st.pop_back(); ds.undo();                          // the oldest A
    }
};

ds.apply must record exactly one undo entry per call, even when nothing changes.

Static to dynamic (binary grouping)

For a static structure (build once, query many) whose queries are decomposable (the answer over a union is a combination of answers over the parts: counts, sums, min, existence), support insertions by keeping groups of sizes $2^{k}$ like the bits of a binary counter. Inserting merges all full low groups with the new item into the first empty slot and rebuilds it.

Each item is rebuilt $O (lo g n)$ times: total $O (B (n) lo g n)$ for build cost $B$ .
A query asks all $O (lo g n)$ groups.

Proof: binary grouping costs $O (B (n) lo g n)$ total and $O (lo g n)$ groups per query

This is exactly a binary counter: group sizes are powers of 2, and inserting an item is a $+ 1$ to the counter, merging (rebuilding) every full low-order group it carries into, exactly as binary addition carries. An item is rebuilt once per carry it participates in; by the standard binary-counter amortized argument, a bit at position $k$ flips (carries) at most once per $2^{k}$ increments, so across $n$ insertions an item is swept into $O (lo g n)$ rebuilds over its lifetime, each rebuild of a size- $2^{k}$ group costing $B (2^{k})$ . Summing geometrically, total cost is $O (B (n) lo g n)$ (or $O (n lo g n \cdot B (1))$ when $B$ is linear). At any moment the number of non-empty groups equals the number of set bits in $n$ ‘s binary representation (the counter value), which is $O (lo g n)$ , so a decomposable query touches $O (lo g n)$ groups. $■$

Deletions: keep a second instance of deleted items and subtract (for counts), or rebuild periodically.
Classic use: dynamic Aho-Corasick (insert patterns, query occurrence counts in texts), dynamic convex hull for queries, KD-tree with insertions.

Batching (sqrt on time)

Process operations in blocks of size $B$ . At the start of each block rebuild a static structure from everything before the block (cost $R$ ), and answer each query in the block from the structure plus a brute-force scan over the at most $B$ pending updates. The total is $O (\frac{q}{B} R + q B)$ , minimised at $B = R$ . It’s the general escape hatch when updates break a fast static structure (Sqrt Decomposition).

Proof: total cost $O (q R / B + q B)$ , minimised at $B = R$

There are $q / B$ blocks, each rebuilt once at cost $R$ : rebuilding contributes $O (\frac{q}{B} R)$ . Within a block, each of its (at most $B$ ) queries scans at most $B$ pending updates, so each block’s query-answering costs $O (B^{2})$ , and there are $q / B$ blocks, contributing $O (\frac{q}{B} \cdot B^{2}) = O (q B)$ . Total: $O (\frac{q R}{B} + q B)$ . Viewing this as a function of $B$ , its derivative w.r.t. $B$ is $- q R / B^{2} + q$ , zero at $B = R$ , and the second derivative is positive there, so $B = R$ minimises the sum (equivalently, by AM-GM, $\frac{q R}{B} + q B \geq 2 q R \cdot q B \cdot \frac{1}{B} = 2 q R$ with equality exactly at $B = R$ ), giving total cost $O (q R)$ . $■$

When you cannot go offline

Genuinely interactive problems, queries that depend on earlier answers (forced-online, blocking exactly these tricks), and streaming settings. Forced-online problems typically XOR the query parameters with the previous answer; when you see that, these techniques are ruled out by design and you need a persistent or truly dynamic structure instead.

whoashish's cp notes

Directory