Parallel Binary Search
Answer many monotone offline queries at once by testing them in batches at shared midpoints.
Parallel Binary Search
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Parallel binary search is the offline version of binary search on answer for many queries at once. The core idea is that queries sharing the same midpoint should also share the data-structure work needed to test that midpoint.
Problem-Driven Motivation
Suppose there are:
updates indexed by time \(1 \dots m\),
many queries asking for the earliest time when some monotone condition becomes true.
If I run a separate binary search for each query, I repeatedly rebuild the same partial data structure for the same midpoints. The asymptotic bottleneck is not the binary search itself. It is the wasted duplication across queries.
Recognition Pattern
Parallel binary search is a strong fit when:
every query asks for a first true / earliest time / smallest index,
the predicate is monotone over an ordered list of updates,
queries are offline,
a prefix of updates can be applied to one reusable checker structure.
Typical signals are:
earliest update when a threshold is reached,
first time two nodes become connected,
offline dynamic processes with many monotone threshold queries.
Derivation
For one query, binary search maintains an interval of candidate answers. For many queries, do the same, but batch all queries that currently test the same midpoint.
At one recursion interval \([L,R]\):
let \(M = \lfloor(L+R)/2\rfloor\),
apply updates \(L \dots M\) to the checker,
test all currently active queries at time \(M\),
send true queries to the left half,
send false queries to the right half.
The important structural saving is that updates \(L \dots M\) are applied once for the whole batch, not once per query.
Worked Problem
Problem.
There are positive point updates \((pos, delta)\). Each query gives \([l,r]\) and a target \(k\), and asks for the earliest update index after which the range sum on \([l,r]\) is at least \(k\).
Why naive fails.
If there are \(10^5\) queries and \(10^5\) updates, running one Fenwick-based binary search per query repeats the same prefix-update work too many times.
Why the predicate is monotone.
All deltas are positive, so range sums only increase as time advances. Once the target is reached, it stays reached.
Key recursion invariant.
For a query currently inside recursion interval \([L,R]\), its stored need means:
How much more sum is still needed after all updates strictly before \(L\) have already been conceptually accounted for.
What happens at midpoint \(M\).
Apply updates \(L \dots M\), measure the gained range sum.
If gained \(\ge \texttt{need}\), the answer lies in \([L,M]\).
Otherwise subtract the gained amount from
needand recurse into \([M+1,R]\).This ``remaining need'' trick is what keeps right-recursion states small and exact.
Implementation Reasoning
The implementation is easiest to trust when organized around three pieces:
one checker structure, here a Fenwick tree,
one recursive function over update intervals,
one query struct that stores its remaining target.
The data structure must be restored after testing the midpoint batch. In the Fenwick version that simply means undoing the updates that were applied for the midpoint.
The code also uses the common dummy-update convention: if a query never becomes true, its answer can be left at the dummy index and interpreted afterward.
Correctness Intuition
Each query moves left or right exactly like an ordinary binary search would, except that many queries share the same midpoint test. Because the remaining-target invariant is updated correctly, the query state after moving right is exactly the state it would have had if all earlier updates had been permanently removed from the search space.
Complexity Analysis
If the checker supports one update or one query in time \(T\), the total complexity is usually \[ O((m+q)\log m \cdot T). \]
For a Fenwick tree this is \(O((m+q)\log m \log n)\).
Common Pitfalls
Using the method on an online problem.
Forgetting that the predicate must be monotone.
Mutating the query state incorrectly when sending it to the right half.
Failing to undo midpoint updates before returning from recursion.
Variants and Failure Modes
Segment trees, DSU, or custom checkers can replace Fenwick trees.
Some implementations use iterative bucket rounds instead of explicit recursion.
If the condition is not monotone in time, parallel binary search is invalid.
Practice Problems
Earliest update when a range sum reaches a threshold.
First time two vertices become connected under edge additions.
Batched monotone threshold queries on an ordered event stream.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<long long> bit;
explicit Fenwick(int n) : n(n), bit(n + 1, 0) {}
void add(int idx, long long delta) {
for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
}
long long prefix_sum(int idx) const {
long long result = 0;
for (; idx > 0; idx -= idx & -idx) result += bit[idx];
return result;
}
long long range_sum(int l, int r) const {
return prefix_sum(r) - prefix_sum(l - 1);
}
};
struct PointUpdate {
int pos;
long long delta;
};
struct ThresholdQuery {
int l;
int r;
long long need;
int id;
};
void solve_parallel_bs(
int left_update,
int right_update,
vector<ThresholdQuery> queries,
const vector<PointUpdate>& updates,
Fenwick& fw,
vector<int>& answer
) {
if (queries.empty()) return;
if (left_update == right_update) {
for (const auto& query : queries) answer[query.id] = left_update;
return;
}
int mid = (left_update + right_update) / 2;
for (int i = left_update; i <= mid; ++i) {
fw.add(updates[i].pos, updates[i].delta);
}
vector<ThresholdQuery> go_left;
vector<ThresholdQuery> go_right;
for (auto query : queries) {
long long gained = fw.range_sum(query.l, query.r);
if (gained >= query.need) {
go_left.push_back(query);
} else {
query.need -= gained;
go_right.push_back(query);
}
}
for (int i = left_update; i <= mid; ++i) {
fw.add(updates[i].pos, -updates[i].delta);
}
solve_parallel_bs(left_update, mid, go_left, updates, fw, answer);
solve_parallel_bs(mid + 1, right_update, go_right, updates, fw, answer);
}
// Example application:
// updates is 1-indexed and updates.back() may be a dummy no-op used to represent "never reached".
vector<int> first_time_range_sum_reaches_target(
int n,
const vector<PointUpdate>& updates,
const vector<ThresholdQuery>& queries
) {
Fenwick fw(n);
vector<int> answer(queries.size(), (int)updates.size() - 1);
solve_parallel_bs(1, (int)updates.size() - 1, queries, updates, fw, answer);
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.