Offline Query Processing

When all queries are known in advance, you may reorder them. That freedom often turns a hard online problem into an easy sweep.

The core idea

online:   answer query i using a structure that supports everything
offline:  sort the queries so that a SIMPLER structure suffices

Competitive programming problems almost always give you every query up front. Always check whether going offline helps before building something complicated.

The main techniques

Technique	Sort by	Structure	Cost
Sweep by coordinate	one coordinate	BIT over the other	$O((n+q)\log n)$
Sweep by value	value threshold	BIT over positions	$O((n+q)\log n)$
Mo’s algorithm	block of $l$, then $r$	an incremental “add/remove” counter	$O((n+q)\sqrt{n})$
Segment tree on time	lifetime intervals	rollback DSU	$O(q\log q\log n)$
CDQ divide and conquer	time, then dimension	BIT	$O(n{\log }^{2}n)$
Parallel binary search	the binary-search step	any checker	$O(\log C)$ rounds
Reverse time	process in reverse	DSU (deletions become unions)	$O(\alpha )$
Tarjan’s offline LCA	DFS order	DSU	$O((n+q)\alpha )$

Sweep by value — the workhorse

“For each query $(l,r,x)$: how many elements in $[l,r]$ are $\le x$?”

// sort array elements by value, queries by x
sort(elems.begin(), elems.end());               // (value, position)
sort(queries.begin(), queries.end(), byX);
int ptr = 0;
BIT bit(n);
for (auto& q : queries) {
    while (ptr < n && elems[ptr].value <= q.x) bit.add(elems[ptr].pos, 1), ptr++;
    ans[q.id] = bit.rangeSum(q.l, q.r);
}

$O((n+q)\log n)$ time, $O(n)$ memory — strictly better than a merge sort tree on both counts, and shorter to write.

The same skeleton answers: count in a value range, sum of elements $\le x$, count of distinct values (with the “last occurrence” trick), and $k$-th smallest (with a BIT descent).

Distinct values in a range

“How many distinct values in $[l,r]$?” — the classic offline problem.

Sort queries by $r$. Sweep $r$ from left to right; for each position keep only its last occurrence marked in the BIT:

map<int,int> last;
int ptr = 0;
for (auto& q : queriesSortedByR) {
    while (ptr <= q.r) {
        if (last.count(a[ptr])) bit.add(last[a[ptr]], -1);   // unmark the old one
        bit.add(ptr, 1);
        last[a[ptr]] = ptr;
        ptr++;
    }
    ans[q.id] = bit.rangeSum(q.l, q.r);
}

$O((n+q)\log n)$. The invariant — each distinct value contributes exactly one mark, at its rightmost occurrence $\le r$ — is what makes it work.

Reverse time

Deletions are hard for DSU but insertions are easy. If the problem only deletes edges or vertices, process the queries backwards and deletions become insertions:

// read all operations, apply all deletions up front,
// then walk backwards re-adding and answering

This is one of the highest-value offline tricks and applies far beyond graphs — anywhere the structure supports “add” but not “remove”.

When you cannot go offline

• Genuinely interactive problems.
• Queries that depend on earlier answers (forced-online problems, common on Codeforces to prevent exactly these techniques).
• Streaming settings.

Forced-online problems typically XOR the query parameters with the previous answer. When you see that, offline techniques are ruled out by design and you need a persistent or truly dynamic structure.

The decision procedure

1. Are all queries known up front? If not, stop.
2. Can sorting by one parameter make a simple structure sufficient? → sweep.
3. Do elements have a lifetime? → segment tree on time + rollback DSU.
4. Is the answer monotone in some parameter? → parallel binary search.
5. Can the answer be maintained incrementally as the range shifts? → Mo’s algorithm.
6. Is it a 3D partial-order counting problem? → CDQ.

See also: Mo’s Algorithm · CDQ Divide and Conquer · Dynamic Connectivity