Appearance
Parallel Binary Search
Quick Revisit
- USE WHEN: Q queries each binary-searching over a shared timeline of events with expensive per-query replay
- REQUIRES: the predicate is monotonic per query — once true at time t, it stays true for all t' > t. Without this, the binary-search decision is invalid and PBS silently returns wrong answers.
- INVARIANT: all queries sharing the same midpoint are checked together in one event-replay pass
- TIME: O(log T · (T · u + Q · q)) where T = number of events, u = per-event update cost (e.g. log N for BIT, α(N) for DSU), q = per-query check cost
- SPACE: O(N + Q)
- CLASSIC BUG: not resetting the data structure between binary search rounds — each round replays from scratch
- PRACTICE: 08-ladder-mixed
AL-41 | Run
Difficulty: [Advanced]Prerequisites: Binary Search, Offline Queries, Fenwick TreeCF Rating Range: 1900--2100
Contents
- 2. Intuition
- 3. C++ STL Reference
- 4. Implementation (Contest-Ready)
- 5. Operations Reference
- 6. Problem Patterns & Tricks
- 7. Contest Cheat Sheet
- 8. Gotchas & Debugging
- 9. Self-Test
- 10. Practice Problems
- 11. Further Reading
Intuition
You have
Hard precondition: the per-query predicate must be monotonic. Once it becomes true at time
Given monotonicity, each query can be solved independently with binary search over
Events: e1 e2 e3 e4 e5 e6 e7 e8 (T = 8)
Q0: binary search [1..8] --> mid=4, replay e1..e4, check --> go right
then [5..8] --> mid=6, replay e1..e6, check --> go left
then [5..5] --> answer = 5
Q1: binary search [1..8] --> mid=4, replay e1..e4, check --> go left
then [1..3] --> mid=2, replay e1..e2, check --> go right
then [3..3] --> answer = 3Each query does
The waste is obvious: Q0 replays
Run all
Instead of each query owning a private binary search, we orchestrate all binary searches in lockstep. In each pass:
- Every query has a current search interval
. Compute . - Group queries by
. Sort or bucket them. - Sweep events
in order. When the sweep reaches time , evaluate the condition for every query whose midpoint is . - Based on the check result, set
(go right) or (go left). - Reset the data structure and repeat.
Each pass processes all
Total:
Parallel Binary Search -- multiple queries, shared timeline:
Timeline: [ 1 2 3 4 5 6 7 8 9 10 ]
Query 1: [---lo---------mid---------hi---] check mid=5
Query 2: [---lo----mid----------hi-------] check mid=4
Query 3: [------lo------mid------hi------] check mid=6
All queries processed in ONE pass through events 1..10
Then each query updates its lo/hi based on check result One PBS iteration:
+------------------+ +-------------------+ +------------------+
| For each query | | Process events | | For each query |
| compute mid = |---->| 1..max_mid in |---->| if check(mid) |
| (lo+hi)/2 | | order, applying | | hi = mid |
| bucket by mid | | to data structure | | else lo = mid+1 |
+------------------+ +-------------------+ +------------------+
^ |
| |
+---------- repeat O(log T) iterations <-------------+Visual Walkthrough
Four queries binary searching over time
Suppose the true answers are: Q0 = 3, Q1 = 5, Q2 = 2, Q3 = 7.
PASS 1 (all queries start with [1, 8], mid = 4)
--------------------------------------------------------
Sweep events e1..e8. At mid = 4, check all queries:
Q0: connected after e1..e4? YES --> hi = 4 [1, 4]
Q1: connected after e1..e4? NO --> lo = 5 [5, 8]
Q2: connected after e1..e4? YES --> hi = 4 [1, 4]
Q3: connected after e1..e4? NO --> lo = 5 [5, 8]
Reset data structure.
PASS 2 (midpoints: Q0=2, Q1=6, Q2=2, Q3=6)
--------------------------------------------------------
Sweep events e1..e8:
At time 2 (mid for Q0, Q2):
Q0: connected after e1..e2? NO --> lo = 3 [3, 4]
Q2: connected after e1..e2? YES --> hi = 2 [1, 2]
At time 6 (mid for Q1, Q3):
Q1: connected after e1..e6? YES --> hi = 6 [5, 6]
Q3: connected after e1..e6? NO --> lo = 7 [7, 8]
Reset data structure.
PASS 3 (midpoints: Q0=3, Q1=5, Q2=1, Q3=7)
--------------------------------------------------------
Sweep events e1..e8:
At time 1: Q2: connected? NO --> lo = 2 [2, 2] DONE
At time 3: Q0: connected? YES --> hi = 3 [3, 3] DONE
At time 5: Q1: connected? YES --> hi = 5 [5, 5] DONE
At time 7: Q3: connected? YES --> hi = 7 [7, 7] DONE
All intervals have lo = hi. Answers: Q0=3, Q1=5, Q2=2, Q3=7. Bucketing queries by mid:
Event timeline: 1 2 3 4 5 6 7 8
| | | | | | | |
Bucket at 2: Q3 | | | | | | |
Bucket at 4: Q1,Q5 | | | | |
Bucket at 6: Q2 | | | |
Bucket at 7: Q4 | |
Process events 1->8, check queries when reaching their midThree passes instead of twelve individual binary search runs. Each pass swept all eight events exactly once.
The Invariant
+-------------------------------------------------------------------+
| INVARIANT: After pass k, every query's search interval [lo, hi] |
| has width <= T / 2^k. The true answer always lies within [lo, hi].|
| After ceil(log2(T)) passes, lo = hi for every query. |
+-------------------------------------------------------------------+Correctness relies on the monotonicity of the predicate. If "condition holds at time
When to Reach for This
Trigger phrases in problem statements:
- "For each of
queries, find the minimum time / threshold / cost such that ..." -- multiple binary searches over the same event axis. - "Events happen in order; each query asks when something first becomes true" -- monotonic predicate over a shared timeline.
- "Offline queries with monotonic answer" -- the answer for each query can be binary searched, and events can be replayed.
Counter-examples (this technique does NOT apply):
- Non-monotonic predicate. If the condition can toggle on and off, binary search is invalid. Use persistent data structures instead.
- Online / forced-online queries. Queries depend on previous answers (e.g., XOR decryption). You cannot batch midpoints.
- Single query. Just do a normal binary search. Parallel binary search is only beneficial for
.
What the Code Won't Teach You
Reading the implementation alone won't reveal why PBS works. The critical structural insight: all
The log factor savings come from amortization. Naive:
Also non-obvious: the data structure reset between passes is not a performance hack -- it is a correctness requirement. Each round must evaluate midpoints against a clean state built from scratch, because queries at different midpoints need the data structure in different states (events
C++ STL Reference
| Function / Class | Header | What it does | Time |
|---|---|---|---|
vector<vector<int>> | <vector> | Group (bucket) query indices by midpoint | |
fill(first, last, val) | <algorithm> | Reset BIT / data structure between passes | |
iota(first, last, val) | <numeric> | Initialize index arrays for indirect sorting | |
sort(first, last, cmp) | <algorithm> | Sort events by time (once, before all passes) | |
__builtin_clz(x) | built-in | Compute |
Implementation (Contest-Ready)
Version 1 -- Minimal: Parallel Binary Search Framework
cpp
#include <bits/stdc++.h>
using namespace std;
struct BIT {
int n;
vector<long long> t;
BIT() : n(0) {}
BIT(int n) : n(n), t(n + 1) {}
void update(int i, long long v) {
for (; i <= n; i += i & -i) t[i] += v;
}
long long query(int i) {
long long s = 0;
for (; i > 0; i -= i & -i) s += t[i];
return s;
}
long long query(int l, int r) { return query(r) - query(l - 1); }
void reset() { fill(t.begin(), t.end(), 0LL); }
};
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
// Events: at time j, add value w to position p.
struct Event { int p; long long w; };
vector<Event> events(m);
for (int j = 0; j < m; j++)
scanf("%d%lld", &events[j].p, &events[j].w);
// Queries: minimum time t such that sum over [l..r] >= k.
struct Query { int l, r; long long k; };
vector<Query> queries(q);
for (int i = 0; i < q; i++)
scanf("%d%d%lld", &queries[i].l, &queries[i].r, &queries[i].k);
vector<int> lo(q, 0), hi(q, m - 1), ans(q, -1);
BIT bit(n);
for (int pass = 0; pass < 20; pass++) { // ceil(log2(m)) <= 20
// Bucket queries by midpoint.
vector<vector<int>> bucket(m);
bool any_active = false;
for (int i = 0; i < q; i++) {
if (lo[i] <= hi[i]) {
int mid = (lo[i] + hi[i]) / 2;
bucket[mid].push_back(i);
any_active = true;
}
}
if (!any_active) break;
bit.reset();
for (int j = 0; j < m; j++) {
// Apply event j.
bit.update(events[j].p, events[j].w);
// Check all queries whose midpoint is j.
for (int i : bucket[j]) {
long long val = bit.query(queries[i].l, queries[i].r);
if (val >= queries[i].k) {
ans[i] = j; // feasible: record and go left
hi[i] = (lo[i] + hi[i]) / 2 - 1;
} else {
lo[i] = (lo[i] + hi[i]) / 2 + 1; // infeasible: go right
}
}
}
}
for (int i = 0; i < q; i++)
printf("%d\n", ans[i] + 1); // 1-indexed time
}Complexity:
passes over all events. - Each pass:
BIT updates ( each) + BIT queries ( each).
Version 2 -- Explained: Minimum Time for Connectivity (DSU)
Classic problem:
cpp
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> par, rnk;
// Track modified nodes for efficient reset.
vector<int> modified;
DSU(int n) : par(n), rnk(n, 0) {
iota(par.begin(), par.end(), 0);
}
int find(int x) {
// Path splitting -- does not prevent reset.
while (par[x] != x) {
int next = par[par[x]];
if (par[x] != next) {
modified.push_back(x);
par[x] = next;
}
x = next;
}
return x;
}
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (rnk[a] < rnk[b]) swap(a, b);
modified.push_back(b);
par[b] = a;
if (rnk[a] == rnk[b]) {
modified.push_back(~a); // sentinel: rank change
rnk[a]++;
}
return true;
}
bool connected(int a, int b) { return find(a) == find(b); }
void reset() {
// Undo all modifications since last reset.
while (!modified.empty()) {
int node = modified.back();
modified.pop_back();
if (node < 0) {
rnk[~node]--;
} else {
par[node] = node;
}
}
}
};
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
struct Edge { int u, v; };
vector<Edge> edges(m);
for (auto& [u, v] : edges) {
scanf("%d%d", &u, &v);
u--; v--; // 0-indexed
}
struct Query { int u, v; };
vector<Query> queries(q);
for (auto& [u, v] : queries) {
scanf("%d%d", &u, &v);
u--; v--;
}
// lo[i] = earliest feasible time, hi[i] = latest time to check.
// ans[i] = best known feasible time (or -1 if never connected).
vector<int> lo(q, 0), hi(q, m - 1), ans(q, -1);
DSU dsu(n);
int passes = 0;
while (passes < 20) {
// Bucket queries by midpoint.
vector<vector<int>> bucket(m);
bool any_active = false;
for (int i = 0; i < q; i++) {
if (lo[i] <= hi[i]) {
bucket[(lo[i] + hi[i]) / 2].push_back(i);
any_active = true;
}
}
if (!any_active) break;
dsu.reset();
for (int j = 0; j < m; j++) {
dsu.unite(edges[j].u, edges[j].v);
for (int i : bucket[j]) {
int mid = (lo[i] + hi[i]) / 2;
if (dsu.connected(queries[i].u, queries[i].v)) {
ans[i] = mid + 1; // 1-indexed answer
hi[i] = mid - 1;
} else {
lo[i] = mid + 1;
}
}
}
// Reset DSU for next pass.
dsu.reset();
passes++;
}
for (int i = 0; i < q; i++)
printf("%d\n", ans[i]);
}Why a resettable DSU instead of rollback? Each pass rebuilds from scratch. We only need to undo everything at the end of a pass, not fine-grained rollback to arbitrary checkpoints. Tracking modified nodes and restoring them is simpler and faster than a full rollback stack.
Complexity:
Operations Reference
| Operation | Time per pass | Passes | Total |
|---|---|---|---|
| Bucket queries by midpoint | |||
| Sweep events (BIT updates) | |||
| Evaluate queries (BIT queries) | |||
| Reset BIT | |||
| BIT variant total | -- | -- | |
| Sweep events (DSU unions) | |||
| Evaluate queries (DSU finds) | |||
| Reset DSU | |||
| DSU variant total | -- | -- |
Problem Patterns & Tricks
Pattern 1: Minimum Time for Threshold (BIT)
Binary search over time. Each pass sweeps all events, updating a BIT. At each midpoint, query the BIT for the range sum and compare to
Template: Version 1 above.
Examples: Meteors (POI 2011), CF 617E.
Pattern 2: Minimum Time for Connectivity (DSU)
Binary search over the edge insertion timeline. Each pass replays all edges into a DSU. At each midpoint, check connectivity.
Template: Version 2 above.
Examples: CF 1923F, USACO Fencing the Cows variants.
Pattern 3: Minimum Cost / Weight Threshold
Edges have weights. Queries ask: "what is the minimum weight
Sort edges by weight (not insertion time). The "time axis" becomes the sorted edge index. Same parallel binary search framework.
cpp
sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
return a.w < b.w;
});
// Now "event j" = "add the j-th lightest edge".
// Each query binary searches over [0, m-1] for minimum j.Examples: CF 1851G (can also be solved with offline DSU, but PBS generalizes to harder variants).
Pattern 4: Assign Values via PBS (Meteors-Style)
Each of
The check function queries total value across all stations of a nation. Use a BIT for range-add, point-query (or range-add, range-query with a difference BIT).
cpp
// Range update: add v to [l, r]
void range_add(BIT& bit, int l, int r, long long v) {
bit.update(l, v);
bit.update(r + 1, -v);
}
// Point query: prefix sum gives value at position i
long long point_query(BIT& bit, int i) {
return bit.query(i);
}This is the canonical PBS problem. Each pass: sweep showers in order, range-add to BIT, check nations at their midpoints.
Example: Meteors (POI 2011).
Pattern 5: PBS + Merge Sort Tree / Wavelet Tree
Sometimes the check function needs "count of elements
Binary search over x for each query.
Each pass: for all queries at midpoint x, query the merge sort
tree for count of elements <= x in [l, r].Example: CF 1093G -- more naturally solved with persistent segment trees, but PBS is an alternative.
Pattern 6: Optimized Reset via Undo Log
Instead of clearing the entire data structure each pass, keep an undo log. After each pass, undo all modifications. This avoids the
The DSU Version 2 above uses this approach with the modified vector. For BIT, track which indices were updated:
cpp
vector<int> touched;
void tracked_update(BIT& bit, int i, long long v) {
touched.push_back(i);
bit.update(i, v);
}
void undo_all(BIT& bit) {
// Zero out only touched cells -- faster than full reset.
// Rebuild would be needed; simpler to just re-zero the BIT.
bit.reset(); // For BIT, full reset is usually fine.
touched.clear();
}Contest Cheat Sheet
+-------------------------------------------------------------------+
| PARALLEL BINARY SEARCH CHEAT SHEET |
+-------------------------------------------------------------------+
| WHEN TO USE: |
| - Q queries, each binary searching over the same event axis |
| - Predicate is monotonic (once true, stays true) |
| - All queries and events are known offline |
| - Independent binary searches would repeat event processing |
+-------------------------------------------------------------------+
| FRAMEWORK: |
| lo[i] = 0, hi[i] = M-1 for all queries i |
| repeat ceil(log2(M)) times: |
| bucket queries by mid = (lo+hi)/2 |
| sweep events 0..M-1: |
| apply event j to data structure |
| for each query i with mid_i == j: |
| if check(i): ans[i]=j, hi[i]=mid-1 |
| else: lo[i]=mid+1 |
| reset data structure |
+-------------------------------------------------------------------+
| COMPLEXITY: |
| BIT: O((M + Q) * log(N) * log(M)) | O(N + M + Q) space |
| DSU: O((M + Q) * alpha(N) * log(M)) | O(N + M + Q) space |
+-------------------------------------------------------------------+
| REMEMBER: |
| - Midpoint must be computed BEFORE the pass (snapshot lo/hi) |
| - Reset data structure between passes (or use undo log) |
| - ans[i] stores last known feasible value; final answer = ans |
| - Handle "no answer" case: if lo > hi and ans == -1, print -1 |
| - 1-index conversion: if events are 0-indexed, ans[i]+1 |
+-------------------------------------------------------------------+Gotchas & Debugging
Midpoint computed during the pass instead of before. Once you update
lo[i]orhi[i]mid-pass, the midpoint changes. Always compute all midpoints before the sweep starts (or bucket queries at the start of each pass). The bucketing approach in Version 1 handles this correctly.Off-by-one in binary search. The standard pitfall. If the predicate is "sum >= k", use
hi = midwhen true andlo = mid + 1when false (finding leftmost true). The implementations above usehi = mid - 1with a separateansvariable to record the last feasible value -- both conventions work, but mixing them is a bug.Forgetting to reset the data structure. Each pass must start from a clean state. If you forget to reset the BIT or DSU, events from the previous pass contaminate the current one, producing wrong midpoint evaluations.
Not handling "never feasible" queries. If a query's condition is never satisfied (e.g., nodes that are never connected),
ansstays at. Make sure your output handles this case. BIT overflow. If events add large values and you sum over many events, the BIT needs
long long. Withevents each adding up to , the sum can reach . DSU reset correctness. When resetting a DSU by undoing modifications, process the undo log in reverse order. The
modifiedvector is a stack -- pop from the back.Circular ranges in Meteors. If events are range-adds on a circular array (
wraps around), split into two BIT updates: [l, N]and[1, r].Debugging tip. Print each query's
after every pass. Verify that intervals shrink monotonically. If any interval grows or oscillates, the check function is not monotonic (or there is a reset bug).
Mental Traps
"PBS is just binary search on each query independently." This is exactly what PBS is NOT. Independent binary searches cost
. PBS runs all searches together -- each round processes all events once and advances every query's interval simultaneously. The savings come from batching the event sweep across all queries. "Parallel means multithreaded." The word "parallel" refers to the
binary searches running in lockstep (simultaneously), not to CPU parallelism or concurrency. Don't let the name mislead you. "If I can binary search the answer, I should use PBS." PBS helps only when (1) you have multiple queries each needing binary search, and (2) the check for all queries at a given midpoint can be done efficiently in one sweep. If each query's individual check is already fast (
), running separate binary searches may be fine. "PBS and CDQ divide-and-conquer are interchangeable." They solve overlapping but distinct problem classes. PBS requires a monotonic predicate per query; CDQ D&C partitions the problem recursively and handles contribution counting. Reaching for the wrong one wastes contest time.
The mistake that teaches
CF Meteors: replaying from scratch per midpoint. My PBS had the right asymptotic complexity on paper but kept TLEing. The bug: within each iteration, I was replaying operations from scratch for every distinct midpoint. If 1000 queries all had mid = 500, I applied operations 1..500 once. But for another 1000 with mid = 501, I cleared the BIT and replayed operations 1..501 from scratch. Fix: within each PBS iteration, sort the midpoints and process them in increasing order, applying operations incrementally (add operation mid to the BIT, don't restart from 1). Reset once per round, not per midpoint. This cut my constant factor ~50x. PBS's power comes from processing events once per round, not once per query.
Debug Drills
Drill 1: Off-by-one in the binary search convergence.
cpp
// Initial setup
vector<int> lo(Q, 0), hi(Q, T); // T operations numbered 0..T-1
for (int iter = 0; iter < 25; iter++) {
// Group queries by midpoint
vector<vector<int>> at(T + 1);
for (int i = 0; i < Q; i++) {
if (lo[i] <= hi[i]) {
int mid = (lo[i] + hi[i]) / 2;
at[mid].push_back(i);
}
}
// Apply operations and check predicates
reset_ds();
for (int t = 0; t <= T; t++) {
if (t > 0) apply_operation(t); // apply operation t
for (int q : at[t]) {
if (check(q)) hi[q] = t - 1;
else lo[q] = t + 1;
}
}
}
// Answer for query i is lo[i]What's wrong?
Operations are numbered 0..T-1, but hi is initialized to T (which is out of range). When mid = T, the code tries apply_operation(T), which doesn't exist. If the predicate is never satisfied, lo[i] ends up as T+1, which is an invalid answer. Fix: initialize hi[i] = T - 1 (last valid operation), and handle the "never satisfied" case separately (if lo[i] > T - 1 after convergence, the answer is "impossible").
Drill 2: Forgetting to reset the data structure between iterations.
cpp
for (int iter = 0; iter < LOG; iter++) {
vector<vector<int>> buckets(T + 1);
for (int i = 0; i < Q; i++) {
if (lo[i] <= hi[i])
buckets[(lo[i] + hi[i]) / 2].push_back(i);
}
// BUG: no reset here
for (int t = 1; t <= T; t++) {
apply(t);
for (int q : buckets[t])
if (check(q)) hi[q] = t - 1;
else lo[q] = t + 1;
}
}What's wrong?
The data structure (BIT, DSU, etc.) is not reset between PBS iterations. After iteration 1, the DS contains all T operations. Iteration 2 starts applying operations again on top of the existing state, effectively doubling the values. Fix: call reset_ds() at the beginning of each iteration, before the inner loop.
Drill 3: Predicate check uses the wrong accumulated state.
cpp
for (int t = 1; t <= T; t++) {
for (int q : buckets[t]) {
if (check(q)) hi[q] = t - 1;
else lo[q] = t + 1;
}
apply(t); // BUG: apply AFTER checking
}What's wrong?
The predicate for queries with midpoint t should be checked after applying operations 1..t. But here, apply(t) happens after checking queries at midpoint t, so those queries only see operations 1..t-1. This shifts every answer by 1. Fix: move apply(t) before the query-checking loop, so queries at midpoint t see the effect of operation t.
Drill 4: Midpoint grouping with lo = t on failure.
cpp
for (int round = 0; round < 20; round++) {
vector<vector<int>> at_mid(T + 1);
for (int i = 0; i < Q; i++) {
if (lo[i] < hi[i]) {
int mid = (lo[i] + hi[i]) / 2;
at_mid[mid].push_back(i);
}
}
// Process events 1..T, at each time t check queries in at_mid[t]
for (int t = 1; t <= T; t++) {
applyEvent(t);
for (int qi : at_mid[t]) {
if (check(qi))
hi[qi] = t; // answer might be earlier
else
lo[qi] = t; // answer is later -- BUG
}
}
resetDataStructure();
}What's wrong?
When the check fails (answer is later than mid), lo[qi] should be set to mid + 1, i.e., t + 1. Setting lo[qi] = t means the next round will include midpoint t again in the search range, potentially causing an infinite loop where lo never advances past a failing midpoint. Fix: lo[qi] = t + 1; (or equivalently, lo[qi] = mid + 1 where mid = t).
Drill 5: Not resetting BIT between rounds.
cpp
for (int round = 0; round < 20; round++) {
// group queries by midpoint...
int eventPtr = 0;
for (int t = 1; t <= T; t++) {
while (eventPtr < M && events[eventPtr].time <= t)
bit.add(events[eventPtr].pos, events[eventPtr].val), eventPtr++;
// check queries at midpoint t...
}
// forgot to reset BIT here!
}What's wrong?
The BIT is never reset between rounds. In round 2, the BIT still contains all events from round 1, so prefix sums are doubled. By round k, values are k times too large, making every query's predicate trivially true. Fix: add bit.reset(); after each round's loop, or undo all insertions at the end of each round. Also, eventPtr should be reset to 0 at the start of each round.
Drill 6: Circular BIT range-add wrap-around.
cpp
// Meteor adds val to circular range [l, r] on array of size n
void addMeteor(int l, int r, long long val) {
bit.add(l, val);
bit.add(r + 1, -val);
// Forgot to handle wrap-around when l > r (circular)
}What's wrong?
When the range wraps around (l > r in a circular array), the range is [l, n] ∪ [1, r]. The code should split it:
cpp
if (l <= r) {
bit.add(l, val);
bit.add(r + 1, -val);
} else {
bit.add(l, val);
bit.add(n + 1, -val);
bit.add(1, val);
bit.add(r + 1, -val);
}Without this, a wrapped range like [8, 3] on an array of size 10 incorrectly adds to positions 8..3 as if it were [3, 8], covering the wrong elements entirely.
Self-Test
Without referring back to the text -- check every box you can confidently do from memory.
- [ ] Explain why running
binary searches "in parallel" saves a log factor compared to running them independently. What is shared across queries in each round? - [ ] State the two preconditions for PBS to apply: what properties must the queries and the predicate have? (Monotonic predicate + independent queries over the same ordered domain.)
- [ ] Write the outer-loop skeleton of PBS from memory -- initialization of
lo/hi, per-round bucketing by midpoint, event sweep, and binary search update -- without filling in problem-specific details. - [ ] Explain why PBS requires offline processing and cannot work when queries arrive online.
- [ ] Derive the PBS time complexity for both the BIT variant (
) and the DSU variant ( ) from the loop structure. - [ ] Identify what goes wrong if you forget to reset the data structure between passes, and describe the visible symptom (intervals not shrinking, wrong answers, non-monotonic convergence).
- [ ] Name a concrete problem (e.g., Meteors POI 2011) where PBS is needed and explain why naive independent binary searches would be too slow.
Practice Problems
Rating Progression
| CF Rating | What to Master |
|---|---|
| 1200 | Understand basic binary search on the answer; recognize monotonic predicates (if condition holds at time t, it holds for all t' > t). |
| 1500 | Implement binary search on time for a single query by replaying operations; understand why this is O(Q * T log T) and too slow. |
| 1800 | Full parallel binary search: maintain [lo, hi] per query, group queries by midpoint, simulate operations once per iteration, check predicates in batch. O((T + Q) log T * f(n)) total. Parallelize: maintain lo[i]/hi[i] per query, group by midpoint, process events in one sweep, update bounds. |
| 2100 | Combine PBS with BIT/segment tree for efficient operation simulation; handle tricky predicates (e.g., "earliest time when connected component has sum >= K"); use PBS as a building block inside CDQ or other offline frameworks. PBS + BIT range-add for weighted events, PBS + DSU with rollback for connectivity, nested PBS. |
| # | Problem | Source | Difficulty | Key Idea |
|---|---|---|---|---|
| 1 | Meteors | POI 2011 | Hard | PBS + BIT range-add; canonical PBS problem |
| 2 | CF 1923F -- Shrink-Ray | CF | Medium-Hard | PBS + prefix sums; shrinking intervals |
| 3 | CF 852D -- Exploration Plan | CF | Hard | PBS + DSU + bipartite matching check |
| 4 | CF 1100E -- Andrew and Taxi | CF | Medium | Binary search on edge weight + topological sort; PBS extends to multi-query |
| 5 | CF 670E -- Correct Bracket Sequence Editor | CF | Medium | PBS on deletion timeline |
| 6 | USACO Plat -- Robotic Cow Herd | USACO | Hard | PBS + priority queue / sorted merge |
| 7 | CF 1039D -- You Are Given a Tree | CF | Very Hard | PBS over block sizes; heavy-light decomposition |
| 8 | Aizu 2645 -- Community | Aizu | Hard | PBS + weighted DSU connectivity |
Further Reading
- CF Blog: Parallel Binary Search (Rezwan.Arefin01) -- tutorial with Meteors walkthrough.
- CF Blog: PBS Tutorial (byvoid) -- offline query survey including PBS.
- cp-algorithms: Binary Search -- prerequisite refresher.
- See:
01-offline-queries.md-- the foundational offline technique that PBS builds on. - See:
04-cdq-divide-and-conquer.md-- offline divide and conquer for multi-dimensional partial order problems. - See:
../../01-data-structures/06-range-query/13-binary-indexed-tree-fenwick.md-- BIT reference for the data structure used in most PBS implementations.