Parallel Binary Search

Why Parallel Binary Search Matters

When processing dynamic systems or event streams, we frequently encounter $N$ independent queries that each seek the exact threshold event $k \in [1, M]$ at which a monotonic predicate becomes satisfied. For example, in competitive programming problems like Meteors or multi-agent resource allocation tasks, $N$ participants each monitor when their accumulated assets cross a personal target threshold across $M$ global distribution events.

Evaluating each query independently using standard binary search requires $O(\log M)$ search iterations per query. Because testing a predicate at time $mid$ typically requires applying $O(M)$ event updates to a range data structure (such as a Fenwick tree or Segment tree), running $N$ isolated binary searches leads to an exorbitant total time complexity of $O(N \cdot M \log M)$, resulting in severe time-limit exceeded (TLE) errors.

Parallel Binary Search (PBS) resolves this bottleneck by shifting the algorithmic perspective: instead of executing $N$ separate binary searches sequentially, it binary searches over the event timeline $[1, M]$ for all $N$ queries simultaneously. By organizing active queries into range-partitioned pools within a global divide-and-conquer framework, Parallel Binary Search applies each event update to a shared data structure only $O(\log M)$ times in total. This reduces the total runtime to $O((N + M) \log M \cdot T_{\text{update}})$, transforming computationally intractable batch threshold searches into efficient $O((N + M) \log M \log K)$ execution routines.

Core Concepts and Terminology

Parallel Binary Search combines binary search over a discrete event range with a dynamic point/range query data structure (such as a Fenwick tree or Segment tree). Understanding its mechanics requires establishing key definitions and invariants.

1. Event Timeline ($1 \dots M$): A sequence of $M$ deterministic updates that modify global or spatial state over time.
2. Query Predicate $C_q(k)$: A monotonic boolean condition for query $q$ that transitions from False to True at some event index $k^*$. Monotonicity guarantees that if $C_q(k) = \text{True}$, then $C_q(k') = \text{True}$ for all $k' > k$.
3. Active Query Pool: The set of queries currently known to have their satisfying threshold within the event interval $[L, R]$.
4. Relative Thresholding: An optimization where, upon advancing a query $q$ to the right subproblem $[mid + 1, R]$, the contribution of events in $[L, mid]$ is subtracted from $q$'s remaining requirement, allowing the shared data structure to be reset to zero at each subproblem.

How Parallel Binary Search Works, Step by Step

The algorithm operates by recursively partitioning the search space $[L, R]$ and query pools through a divide-and-conquer function solve(L, R, active_queries):

Step 1: Base Case Check

If $L = R$, every query $q \in \text{active\_queries}$ has found its earliest satisfying event index. Record ans[q.id] = L and return.

Step 2: Mid-Point Range Expansion

Compute $mid = \lfloor (L + R) / 2 \rfloor$. Iterate through all events from index $L$ up to $mid$, applying their updates to the shared Fenwick tree.

Step 3: Query Pool Partitioning

Iterate through each query $q \in \text{active\_queries}$:

• Query the current accumulated value at $q$'s monitored position(s) from the Fenwick tree.
• If accumulated value $\ge req[q]$: $q$ is satisfied within $[L, mid]$. Add $q$ to left_queries.
• Otherwise: $q$ requires events beyond $mid$. Update $req[q] \leftarrow req[q] - \text{accumulated\_value}$ and add $q$ to right_queries.

Step 4: Data Structure Rollback

Iterate back through events from $L$ to $mid$, applying inverse updates (subtracting values) to reset the Fenwick tree to zero.

Step 5: Recursive Subproblems

Recurse on solve(L, mid, left_queries) and solve(mid + 1, R, right_queries).

The control flow logic for Parallel Binary Search is structured as follows:

flowchart TD
A[Start: solve L, R, active_queries] --> B{active_queries is empty?}
B -- Yes --> C[Return]
B -- No --> D{L == R?}
D -- Yes --> E[Set ans q.id = L for all q in active_queries]
E --> F[Return]
D -- No --> G[Compute mid = L + R / 2]
G --> H[Apply Events L ... mid into Fenwick Tree]
H --> I[Initialize left_queries and right_queries]
I --> J[For each q in active_queries: Query Fenwick Tree]
J --> K{val >= q.req?}
K -- Yes --> L[Push q into left_queries]
K -- No --> M[q.req = q.req - val; Push q into right_queries]
L --> N[Finished evaluating active_queries]
M --> N
N --> O[Rollback/Undo Events L ... mid from Fenwick Tree]
O --> P[Recurse: solve L, mid, left_queries]
P --> Q[Recurse: solve mid+1, R, right_queries]
Q --> R[Return]

Worked Example with a Full Trace

Let us trace a concrete problem instance end-to-end.

Problem Setup:

• $N = 3$ Queries ($q_0, q_1, q_2$)
• $M = 4$ Events ($e_1, e_2, e_3, e_4$)
• Positions $0, 1, 2$

Events:

• Event $1$: Add $+5$ to pos $0$, Add $+3$ to pos $1$
• Event $2$: Add $+4$ to pos $1$, Add $+2$ to pos $2$
• Event $3$: Add $+4$ to pos $0$, Add $+5$ to pos $2$
• Event $4$: Add $+3$ to pos $1$, Add $+2$ to pos $0$

Query Requirements:

• Query $0$ ($q_0$): monitors pos $0$, target requirement = $8$
• Query $1$ ($q_1$): monitors pos $1$, target requirement = $10$
• Query $2$ ($q_2$): monitors pos $2$, target requirement = $6$

Implementation in Python, C++, and Java

Below are complete, copy-paste-runnable implementations in Python, C++, and Java. All three use identical algorithm logic, process the exact same sample dataset, and produce identical terminal output.

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, idx, val):
        i = idx + 1
        while i <= self.size:
            self.tree[i] += val
            i += i & -i

    def prefix_query(self, idx):
        if idx < 0:
            return 0
        i = idx + 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def point_query(self, idx):
        return self.prefix_query(idx) - self.prefix_query(idx - 1)


class Event:
    def __init__(self, pos, val):
        self.pos = pos
        self.val = val


class Query:
    def __init__(self, q_id, pos, req):
        self.q_id = q_id
        self.pos = pos
        self.req = req


def solve_parallel_binary_search():
    # Setup sample data (1-indexed event timeline 1..4)
    events = [
        [],  # 1-indexed padding
        [Event(0, 5), Event(1, 3)],  # Event 1
        [Event(1, 4), Event(2, 2)],  # Event 2
        [Event(0, 4), Event(2, 5)],  # Event 3
        [Event(1, 3), Event(0, 2)]   # Event 4
    ]

    queries = [
        Query(0, 0, 8),
        Query(1, 1, 10),
        Query(2, 2, 6)
    ]

    num_queries = len(queries)
    num_events = len(events) - 1
    ans = [0] * num_queries
    bit = FenwickTree(3)

    def pbs(l, r, active_queries):
        if not active_queries:
            return
        if l == r:
            for q in active_queries:
                ans[q.q_id] = l
            return

        mid = (l + r) // 2

        # Apply events from l to mid
        for e_idx in range(l, mid + 1):
            for update in events[e_idx]:
                bit.add(update.pos, update.val)

        left_queries = []
        right_queries = []

        # Evaluate active queries
        for q in active_queries:
            current_val = bit.point_query(q.pos)
            if current_val >= q.req:
                left_queries.append(q)
            else:
                q.req -= current_val
                right_queries.append(q)

        # Undo events from l to mid (rollback)
        for e_idx in range(l, mid + 1):
            for update in events[e_idx]:
                bit.add(update.pos, -update.val)

        pbs(l, mid, left_queries)
        pbs(mid + 1, r, right_queries)

    pbs(1, num_events, queries)

    for i in range(num_queries):
        print(f"Query {i}: satisfied at event {ans[i]}")


if __name__ == "__main__":
    solve_parallel_binary_search()

#include <iostream>
#include <vector>

struct Event {
    int pos;
    int val;
};

struct Query {
    int q_id;
    int pos;
    int req;
};

class FenwickTree {
    int size;
    std::vector<int> tree;
public:
    explicit FenwickTree(int size) : size(size), tree(size + 1, 0) {}

    void add(int idx, int val) {
        for (int i = idx + 1; i <= size; i += i & -i) {
            tree[i] += val;
        }
    }

    int prefix_query(int idx) const {
        if (idx < 0) return 0;
        int sum = 0;
        for (int i = idx + 1; i > 0; i -= i & -i) {
            sum += tree[i];
        }
        return sum;
    }

    int point_query(int idx) const {
        return prefix_query(idx) - prefix_query(idx - 1);
    }
};

void pbs(int l, int r, std::vector<Query>& active_queries,
         const std::vector<std::vector<Event>>& events,
         FenwickTree& bit, std::vector<int>& ans) {
    if (active_queries.empty()) return;

    if (l == r) {
        for (const auto& q : active_queries) {
            ans[q.q_id] = l;
        }
        return;
    }

    int mid = l + (r - l) / 2;

    for (int e_idx = l; e_idx <= mid; ++e_idx) {
        for (const auto& update : events[e_idx]) {
            bit.add(update.pos, update.val);
        }
    }

    std::vector<Query> left_queries;
    std::vector<Query> right_queries;

    for (auto q : active_queries) {
        int current_val = bit.point_query(q.pos);
        if (current_val >= q.req) {
            left_queries.push_back(q);
        } else {
            q.req -= current_val;
            right_queries.push_back(q);
        }
    }

    for (int e_idx = l; e_idx <= mid; ++e_idx) {
        for (const auto& update : events[e_idx]) {
            bit.add(update.pos, -update.val);
        }
    }

    pbs(l, mid, left_queries, events, bit, ans);
    pbs(mid + 1, r, right_queries, events, bit, ans);
}

int main() {
    std::vector<std::vector<Event>> events = {
        {}, // 1-indexed padding
        {{0, 5}, {1, 3}}, // Event 1
        {{1, 4}, {2, 2}}, // Event 2
        {{0, 4}, {2, 5}}, // Event 3
        {{1, 3}, {0, 2}}  // Event 4
    };

    std::vector<Query> queries = {
        {0, 0, 8},
        {1, 1, 10},
        {2, 2, 6}
    };

    int num_queries = static_cast<int>(queries.size());
    int num_events = static_cast<int>(events.size()) - 1;
    std::vector<int> ans(num_queries, 0);
    FenwickTree bit(3);

    pbs(1, num_events, queries, events, bit, ans);

    for (int i = 0; i < num_queries; ++i) {
        std::cout << "Query " << i << ": satisfied at event " << ans[i] << "\n";
    }

    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Event {
        int pos;
        int val;
        Event(int pos, int val) {
            this.pos = pos;
            this.val = val;
        }
    }

    static class Query {
        int qId;
        int pos;
        int req;
        Query(int qId, int pos, int req) {
            this.qId = qId;
            this.pos = pos;
            this.req = req;
        }
    }

    static class FenwickTree {
        private final int size;
        private final int[] tree;

        public FenwickTree(int size) {
            this.size = size;
            this.tree = new int[size + 1];
        }

        public void add(int idx, int val) {
            for (int i = idx + 1; i <= size; i += i & -i) {
                tree[i] += val;
            }
        }

        public int prefixQuery(int idx) {
            if (idx < 0) return 0;
            int sum = 0;
            for (int i = idx + 1; i > 0; i -= i & -i) {
                sum += tree[i];
            }
            return sum;
        }

        public int pointQuery(int idx) {
            return prefixQuery(idx) - prefixQuery(idx - 1);
        }
    }

    private static void pbs(int l, int r, List<Query> activeQueries,
                            List<List<Event>> events,
                            FenwickTree bit, int[] ans) {
        if (activeQueries.isEmpty()) return;

        if (l == r) {
            for (Query q : activeQueries) {
                ans[q.qId] = l;
            }
            return;
        }

        int mid = l + (r - l) / 2;

        for (int eIdx = l; eIdx <= mid; eIdx++) {
            for (Event update : events.get(eIdx)) {
                bit.add(update.pos, update.val);
            }
        }

        List<Query> leftQueries = new ArrayList<>();
        List<Query> rightQueries = new ArrayList<>();

        for (Query q : activeQueries) {
            int currentVal = bit.pointQuery(q.pos);
            if (currentVal >= q.req) {
                leftQueries.add(q);
            } else {
                q.req -= currentVal;
                rightQueries.add(q);
            }
        }

        for (int eIdx = l; eIdx <= mid; eIdx++) {
            for (Event update : events.get(eIdx)) {
                bit.add(update.pos, -update.val);
            }
        }

        pbs(l, mid, leftQueries, events, bit, ans);
        pbs(mid + 1, r, rightQueries, events, bit, ans);
    }

    public static void main(String[] args) {
        List<List<Event>> events = new ArrayList<>();
        events.add(new ArrayList<>()); // 1-indexed padding

        List<Event> e1 = new ArrayList<>();
        e1.add(new Event(0, 5)); e1.add(new Event(1, 3));
        events.add(e1);

        List<Event> e2 = new ArrayList<>();
        e2.add(new Event(1, 4)); e2.add(new Event(2, 2));
        events.add(e2);

        List<Event> e3 = new ArrayList<>();
        e3.add(new Event(0, 4)); e3.add(new Event(2, 5));
        events.add(e3);

        List<Event> e4 = new ArrayList<>();
        e4.add(new Event(1, 3)); e4.add(new Event(0, 2));
        events.add(e4);

        List<Query> queries = new ArrayList<>();
        queries.add(new Query(0, 0, 8));
        queries.add(new Query(1, 1, 10));
        queries.add(new Query(2, 2, 6));

        int numQueries = queries.size();
        int numEvents = events.size() - 1;
        int[] ans = new int[numQueries];
        FenwickTree bit = new FenwickTree(3);

        pbs(1, numEvents, queries, events, bit, ans);

        for (int i = 0; i < numQueries; i++) {
            System.out.println("Query " + i + ": satisfied at event " + ans[i]);
        }
    }
}

Complexity, Correctness, and Invariants

Time Complexity Analysis

• Recursion Tree Depth: The search space $[1, M]$ is halved at each level, giving a total tree depth of $O(\log M)$.
• Work Per Recursion Level: Across all nodes at recursion depth $d$, each query belongs to exactly one active pool, meaning queries are tested $O(N)$ times per level. Similarly, each event index is involved in range insertions and rollbacks $O(M)$ times across all nodes at depth $d$.
• Total Time Complexity: $O((N \cdot T_{\text{query}} + M \cdot T_{\text{update}}) \log M)$. Using a Fenwick tree of size $K$, $T_{\text{query}} = T_{\text{update}} = O(\log K)$, yielding an overall time complexity of $O((N + M) \log K \log M)$.

Space Complexity Analysis

• Auxiliary Memory: $O(N + M + K)$ for storing query structures, event lists, answer arrays, and the Fenwick tree.
• Stack Space: Recursion depth requires $O(\log M)$ call stack space.

Variants, Pitfalls, and Optimizations

Common Variants

1. Range Updates via Range Fenwick Tree: When events apply updates across continuous position ranges $[l, r]$, a Range-Update Range-Query Fenwick tree or Segment tree with lazy propagation can be substituted without altering the PBS control flow.
2. Dynamic Graph Connectivity (PBS + Rollback DSU): Used to determine the exact edge insertion time at which two vertices become connected. Instead of a Fenwick tree, a Disjoint Set Union with Rollback (union-by-size without path compression) is used to undo edge additions during tree unwind.

Common Pitfalls

1. Forgetting State Rollback: Failing to undo event updates before returning or recursing leaves dirty state in the shared data structure, corrupting evaluations in sibling nodes.
2. Off-by-One Event Timeline Bounds: Setting the search bounds to $[0, M-1]$ instead of $[1, M]$ can cause indexing bugs when subtracting relative requirements or handling 1-based Fenwick trees.
3. Unreachable Queries: Queries whose requirements exceed the total contribution of all $M$ events will attempt to resolve beyond $M$. Handled by assigning a fallback answer (e.g., $-1$ or $\infty$) when $L = R = M$ and $req[q] > 0$.

Practice Problems and Real-World Use

Parallel Binary Search is widely applicable in competitive programming, dynamic graph connectivity, and real-time telemetry systems.