iv. Parallel Binary Search

$q$ queries each ask “after how many of the $m$ operations does my condition first become true?”, where the condition is monotone in time. Binary searching each query separately rebuilds the structure $O(q\log m)$ times. Doing all the searches together sweeps the operations only $O(\log m)$ times.

Iterative form

vector<int> lo(q, 1), hi(q, m + 1);                 // answer in [lo, hi]; m + 1 = never
for (bool changed = true; changed; ) {
    changed = false;
    vector<vector<int>> at(m + 2);
    for (int i = 0; i < q; i++) if (lo[i] < hi[i]) at[(lo[i] + hi[i]) / 2].push_back(i), changed = true;
    reset();                                         // fresh structure (or rollback to empty)
    for (int t = 1; t <= m; t++) {
        apply(t);
        for (int i : at[t]) {
            if (check(i)) hi[i] = t; else lo[i] = t + 1;
        }
    }
}

The cost is $O(\log m)$ rounds, each costing $O(m\cdot \text{apply}+q\cdot \text{check}+\text{reset})$.

Proof: correctness and $O(\log m)$ rounds

Correctness. The invariant maintained before each round is: for every query $i$, the true answer lies in $[l{o}_i,h{i}_i]$ (initially $[1,m+1]$, trivially true since the answer is some operation index or “never” $=m+1$). Within a round, the sweep from $t=1$ to $m$ applies operations in their true order, so when query $i$‘s midpoint is reached, check(i) evaluates the condition against exactly the state after the first ${\text{mid}}_i$ operations — the correct state to test monotonicity at that point. By monotonicity, check(i) true means the answer is $\le {\text{mid}}_i$ (narrowing to $h{i}_i={\text{mid}}_i$, keeping the true answer inside, since it was $\le h{i}_i$ before and is now known $\le {\text{mid}}_i\le h{i}_i$), and false means the answer is $>{\text{mid}}_i$ (narrowing to $l{o}_i={\text{mid}}_i+1$, again keeping the true answer inside). So the invariant is preserved every round. Round count. Each query’s interval length is halved (standard binary search), so after $\lceil {\log }_2(m+1)\rceil$ rounds every $l{o}_i=h{i}_i$ and the loop’s changed flag goes false. $■$

The structure only needs to be built incrementally (insert-only). That’s the main advantage over offline-deletion techniques: a plain DSU or BIT suffices.

Recursive form (overall binary search), a.k.a. fracturing search

Recurse on the answer interval $[L,R)$ together with the queries whose answer lies there and the operations with time in $[L,R)$. Apply the operations in $[L,M)$, split the queries by check, undo, and recurse left and right. The total work is $O((m+q)\log m)$ applications, and there’s no global reset per round. Used for:

“Fracturing search” is the name this exact recursion goes by in some references (e.g. USACO Guide); it’s the same algorithm, just framed slightly more generally than “parallel binary search” strictly defined. The iterative form above needs every query’s check to be the same monotone timeline (one shared direction of “becomes true”); the recursive form only needs each query’s own predicate to be monotone within the interval it’s currently routed to — nothing requires all queries to share one global answer axis or even the same comparison direction, since each query is independently split left/right by its own check at its own recursion node. That’s why it comes up for problems with per-query thresholds that aren’t literally “after which timestep,” as long as each one is checkable against the same incrementally-built structure.

Proof: $O((m+q)\log m)$ total applications

The recursion tree has depth $O(\log m)$ (the answer interval halves each level). At each node covering answer-range $[L,R)$, the operations with time in $[L,M)$ are applied once — and since each operation’s time value belongs to a unique, strictly shrinking nested sequence of intervals as the recursion descends (it’s “active” at exactly the nodes on the path from the root to the leaf containing its time, by the same one-level-of-separation argument as plain divide and conquer), each of the $m$ operations is applied at most once per depth, giving $O(m\log m)$ total operation-applications across the whole recursion. Each of the $q$ queries is routed to exactly one child at each node (split by check), so each query is checked once per depth it’s still “alive” at, $O(q\log m)$ total. Summing: $O((m+q)\log m)$. $■$

• range $k$-th smallest with point updates: the answer is a value; operations are “insert/delete value at position”; check is a BIT range count compared with $k$. $O((n+q){\log }^{2}n)$, offline, no persistence.
• first time each region reaches a quota (POI “Meteors”): the operations are range adds on a circular array, the queries ask when an owner’s total reaches its demand.

Examples

Query	apply	check
first edge index after which $u,v$ are connected	DSU union	same component
first time a component containing $v$ has size $\ge k$	DSU union	size
first time the graph restricted to edges so far becomes non-bipartite, per query vertex set	DSU with parity	parity conflict
$k$-th smallest in $a[l..r]$ (static)	insert positions of values in sorted order into a BIT	count in $[l,r]\ge k$
first day a country’s collected total meets its demand	range add (BIT)	sum over its stations, capped to avoid overflow
minimum bottleneck between $u$ and $v$	edges sorted by weight, DSU	connected
minimum capacity for all flows to succeed	add an edge	max-flow value
first round in which a player is eliminated	apply a round	evaluate a condition

For “min bottleneck between $u$ and $v$” there’s also an online alternative: the Kruskal reconstruction tree, where the answer is the weight at $\mathrm{LCA}(u,v)$ (Kruskal Reconstruction Tree).

Parallel binary search vs. the alternatives

Technique	Handles	Cost	Structure needed
Parallel binary search	”when does the answer flip”, many queries	$O(\log m)$ rebuilds	incrementally buildable (add-only)
Segment tree on time	queries at arbitrary times, add and remove	$O(\log m)$ per operation	rollback-able
CDQ	multi-dimensional dominance	$O(n{\log }^{2}n)$	BIT
Persistent structures	online historical queries	$O(\log n)$ per query	persistent
Independent binary searches per query	few queries	$O(q\log m\cdot \text{rebuild})$	rebuildable

The distinguishing feature: parallel binary search needs only an incrementally buildable structure, not a rollback-able or persistent one — a plain DSU or BIT suffices where offline dynamic connectivity would need rollback.

Requirements and pitfalls

• The predicate must be monotone in time (once true, always true). Check it before coding.
• Reset fully between rounds; leftover state is the usual bug. With a rollback DSU you can undo to empty instead.
• Use the sentinel $m+1$ for “never” and test it at the end.
• Overflow in accumulated checks (sums of demands): cap at the threshold.
• The rounds are independent, so this parallelises trivially across threads if that is ever useful.