Parallel Binary Search

Tutorial

Pseudocode

Let $\text{event[i]}$ corresponds to some stuff that needed be done at that particular index $i$ ($lo \leq i \leq hi$)

For all $\mathcal{O}(\log MaxAns)$ levels, we maintain independent data structure $\text{DS[level]}$. Associated with every data structure we have our monotonic function $\text{DS[level].f()}$ and $\text{DS[level].add()}$ for maintaining ongoing events at that level.

A pseudocode for parallel binary search looks something like this:

parallel_binary_search(l, r, level, candidate):
    m = candidate.size

	if m == 1:
        for i = 0 to m-1:
        ans[candidate[i]] = l

    candidate.clean()
    return

    mid = floor((l + r) / 2)

    while pointer[level] <= mid:
        DS[level].add(event[pointer[level]])
        pointer[level] = pointer[level] + 1


    for i = 0 to m-1:
        if DS[level].f(lo, mid, candidate[i]) == True:
            satisfied_candidate.add(candidate[i])
        else:
            unsatisfied_candidate.add(candidate[i])

    candidate.clean()

    parallel_binary_search(l, mid, level + 1, satisfied_candidate)
    parallel_binary_search(mid + 1, r, level + 1, unsatisfied_candidate)

// Calculating answers for the range [lo, hi] where `relevant_candidate` belongs to that range
parallel_binary_search(lo, hi, 0, relevant_candidate)

Generalized Complexity

Copy
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAX_LOG = 20;

struct Disjoint_Set_Union {
	int n;

Problems