Skip to content

Parallel Binary Search

Introduction

In competitive programming, some problems can be solved using binary search. However, when such problems involve multiple queries and we perform binary search for each query directly, it may lead to TLE. In such cases, parallel binary search (also known as "overall binary search" or "parallel binary search") is used. The main idea of parallel binary search is to process multiple queries together (hence it is an offline algorithm).

Problems solvable by parallel binary search must satisfy the following properties:

  1. The answer to each query is binary-searchable.
  2. Modifications that affect the decision of the answer are mutually independent; modifications do not interfere with each other's effects.
  3. If a modification affects the decision of the answer, its contribution is a fixed value independent of the decision criterion.
  4. The contributions satisfy commutativity, associativity, and are additive.
  5. The problem allows an offline algorithm.

— From "A Brief Discussion on Several Non‑Classical Solutions for Data Structure Problems" by Fio.

Explanation

Let \([l,r]\) be the range of possible answer values, and \([L,R]\) be the domain of operations/indices considered (i.e, when computing the answer, only operations and queries with indices in \([L,R]\) are considered, and the answers for queries lie in \([l,r]\)).

  • First, we store all operations in chronological order in an array, then begin the divide-and-conquer.
  • At each level of recursion, we use a data structure (commonly a Fenwick Tree) to determine the relationship between the current query's answer and the midpoint \(mid\).
  • Based on whether the query's answer is \(\le mid\) or \(> mid\), we split the current sequence of operations into two parts, \(q_1\) and \(q_2\), and recursively process each part.
  • When \(l = r\), we have found the answer; record it and return.

Note that during parallel binary search, if the current value range being processed is \([l,r]\), then queries whose final answer does not lie in \([l,r]\) will be handled in other branches.

Procedure

Notes:

  1. For readability, the code may not follow the style commonly used in actual contests.
  2. If a piece of code seems difficult to understand, please refer to explanations of earlier problems, as previously explained content will not be repeated to save space.

Starting with ordinary binary search:

Query the k-th smallest element globally

Problem 1 Given a sequence, query the \(k\)-th smallest number.

Certainly, we can sort directly. But what about using binary search? We can use a data structure to record how many numbers fall into each value range, then guess with binary search and verify using the data structure.

Problem 2 Given a sequence, answer multiple queries for the \(k\)-th smallest number.

We could perform binary search for each query individually; however, we can also process all queries together with a single binary search.

Consider the essence of binary search: suppose we want to guess a number in \([l,r]\). After guessing, we learn whether the guess is too high, too low, or correct. We could enumerate from \(l\) to \(r\), but a better approach is binary search: guess \(m = \lfloor\frac{l + r}{2}\rfloor\), verify correctness for \(m\), then adjust the bounds. This yields \(O(\log n)\) per query. If there are \(q\) queries, the total time is \(O(q\log n)\).

Looking back, for all current queries, we can guess that all answers are \(mid\), then verify for each query whether its answer should be \(\le mid\) or \(> mid\), and split the queries into two groups (≤ / >). For each group, continue binary search. Note: if a query's answer is greater than \(mid\), before moving it to the right group, we must update its \(k\); i.e, if there are \(t\) numbers \(\le mid\) in the current sequence, then when splitting, the query actually asks for the \((k - t)\)-th smallest in the right interval. If for a group \(l = r\), end the binary search for that group. Using knowledge of segment trees, each time we split the entire possible answer range \([1,n]\) (assuming discretization) into several parts; such splitting occurs \(O(\log n)\) times, and each split processes the entire operation sequence once. If processing the whole sequence and supporting the corresponding query takes \(O(T)\), then parallel binary search runs in \(O(T\log n)\).

Reference code:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct Query {
  int id, k;  // query id, and k (k-th smallest)
};

int ans[N], a[N];  // ans[i] = answer for query i, a = original array
int val[N], cnt[N];  // after discretization, record values and their counts (assumed prepared)

// return count of numbers in original array with values in [l,r]
int check(int l, int r) {
  int res = 0;
  for (int i = l; i <= r; i++) {
    res += cnt[i];
  }
  return res;
}

// parallel binary search
void solve(int l, int r, vector<Query> q) {
  int m = (l + r) / 2;
  if (l == r) {
    for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = val[l];
    return;
  }
  vector<Query> q1, q2;
  int t = check(l, m);
  for (unsigned i = 0; i < q.size(); i++) {
    if (q[i].k <= t)
      q1.push_back(q[i]);
    else
      q[i].k -= t, q2.push_back(q[i]);
  }
  solve(l, m, q1), solve(m + 1, r, q2);
  return;
}

Query the k-th smallest element in a subarray

Problem 3 Given a sequence, answer multiple queries for the \(k\)-th smallest number in a given subarray.

If we follow the previous method, the check function would become too slow because of the subarray queries. Still consider the relationship between a query and the midpoint \(m\): if there are \(t\) numbers \(\le m\) in the query interval, and the query asks for the \(k\)-th smallest, then if \(k \le t\), the answer should be \(\le m\); otherwise, it should be \(> m\). (Watch for boundary issues.) Here we need to count how many numbers in a subarray are \(\le\) a given value, i.e, point additions and range sums, which can be handled quickly with a Fenwick Tree. To improve efficiency, only numbers whose values lie in the current value range \([l,r]\) are considered; i.e, before recursing further, we split not only the queries but also the current numbers based on their value range.

Key part of reference code:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct Num {
  int p, x;
};  // number at position p with value x

struct Query {
  int l, r, k, id;
};  // query id asks for k-th smallest in [l,r]

int ans[N];
void add(int p, int x);  // Fenwick Tree: add x at position p
int query(int p);        // Fenwick Tree: prefix sum up to p
void clear();            // Fenwick Tree: clear

void solve(int l, int r, vector<Num> a, vector<Query> q)
// a contains numbers from the original array with values in [l,r]
{
  int m = (l + r) / 2;
  if (l == r) {
    for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = l;
    return;
  }
  vector<Num> a1, a2;
  vector<Query> q1, q2;
  for (unsigned i = 0; i < a.size(); i++)
    if (a[i].x <= m)
      a1.push_back(a[i]), add(a[i].p, 1);
    else
      a2.push_back(a[i]);
  for (unsigned i = 0; i < q.size(); i++) {
    int t = query(q[i].r) - query(q[i].l - 1);
    if (q[i].k <= t)
      q1.push_back(q[i]);
    else
      q[i].k -= t, q2.push_back(q[i]);
  }
  clear();
  solve(l, m, a1, q1), solve(m + 1, r, a2, q2);
  return;
}

Below is a more contest‑style implementation for the problem 【Template】Persistent Segment Tree 2 using parallel binary search.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 200020;
int n, m;
int ans[N];
// BIT begin
int t[N];
int a[N];

int sum(int p) {
  int ans = 0;
  while (p) {
    ans += t[p];
    p -= p & (-p);
  }
  return ans;
}

void add(int p, int x) {
  while (p <= n) {
    t[p] += x;
    p += p & (-p);
  }
}

// BIT end
int tot = 0;

struct Query {
  int l, r, k, id, type;  // set values to -1 when they are not used!
} q[N * 2], q1[N * 2], q2[N * 2];

void solve(int l, int r, int ql, int qr) {
  if (ql > qr) return;
  if (l == r) {
    for (int i = ql; i <= qr; i++)
      if (q[i].type == 2) ans[q[i].id] = l;
    return;
  }
  int mid = (l + r) / 2, cnt1 = 0, cnt2 = 0;
  for (int i = ql; i <= qr; i++) {
    if (q[i].type == 1) {
      if (q[i].l <= mid) {
        add(q[i].id, 1);
        q1[++cnt1] = q[i];
      } else
        q2[++cnt2] = q[i];
    } else {
      int x = sum(q[i].r) - sum(q[i].l - 1);
      if (q[i].k <= x)
        q1[++cnt1] = q[i];
      else {
        q[i].k -= x;
        q2[++cnt2] = q[i];
      }
    }
  }
  // rollback changes
  for (int i = 1; i <= cnt1; i++)
    if (q1[i].type == 1) add(q1[i].id, -1);
  // move them to the main array
  for (int i = 1; i <= cnt1; i++) q[i + ql - 1] = q1[i];
  for (int i = 1; i <= cnt2; i++) q[i + cnt1 + ql - 1] = q2[i];
  solve(l, mid, ql, cnt1 + ql - 1);
  solve(mid + 1, r, cnt1 + ql, qr);
}

pair<int, int> b[N];
int toRaw[N];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  // read and discrete input data
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    b[i].first = x;
    b[i].second = i;
  }
  sort(b + 1, b + n + 1);
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (b[i].first != b[i - 1].first) cnt++;
    a[b[i].second] = cnt;
    toRaw[cnt] = b[i].first;
  }
  for (int i = 1; i <= n; i++) {
    q[++tot] = {a[i], -1, -1, i, 1};
  }
  for (int i = 1; i <= m; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    q[++tot] = {l, r, k, i, 2};
  }
  solve(0, cnt + 1, 1, tot);
  for (int i = 1; i <= m; i++) cout << toRaw[ans[i]] << '\n';
}

Dynamic k-th smallest in a subarray

Problem 4 Dynamic Rankings Given a sequence, support point updates and queries for the \(k\)-th smallest in a subarray.

An update can be thought of as removing a number and then inserting another. For convenience, we unify queries and modifications as "operations". Because later operations depend on earlier ones, we cannot separate counting and processing queries as in Problem 3. Therefore, we store all operations in one array, distinguished by a type field, and process them in order. To facilitate the Fenwick Tree, an update can be split into a removal operation and an insertion operation.

Optimizations

  1. Notice that during classification of operations, only the order of operations changes, so we can operate directly on the original array. In practice, during recursion we replace the operation arrays \(q, a\) with a single large global array, and the recursion parameters become \(L, R\), the interval in the global array currently being processed. Use temporary arrays to record the classification, and write them back to the original array before recursing.
  2. Clearing the Fenwick Tree each time would cause a time explosion. Instead, we can record the positions modified during this step (already done by the temporary arrays mentioned in 1), and after finishing this step, add \(-1\) to those positions to quickly clear.
  3. Initialization of the sequence can be simplified as insertion operations.

Key part of reference code:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct Opt {
  int x, y, k, type, id;
  // For a query: type = 1, x, y are the interval bounds, k is the k-th smallest.
  // For an update: type = 0, x is the position, y is the new value,
  // k indicates whether this operation is an insertion (1) or removal (-1), used when updating the Fenwick Tree.
  // id records the original order of the operation, because order gets scrambled during recursion.
};

Opt q[N], q1[N], q2[N];
// q holds all operations,
// during recursion, operations going left are stored in q1, right in q2.
int ans[N];
void add(int p, int x);
int query(int p);  // Fenwick Tree functions, same as in Problem 3

void solve(int l, int r, int L, int R)
// current value range [l,r], processing operations in [L,R]
{
  if (l > r || L > R) return;
  int cnt1 = 0, cnt2 = 0, m = (l + r) / 2;
  // cnt1, cnt2: number of operations going left / right
  if (l == r) {
    for (int i = L; i <= R; i++)
      if (q[i].type == 1) ans[q[i].id] = l;
    return;
  }
  for (int i = L; i <= R; i++)
    if (q[i].type == 1) {  // query: classify
      int t = query(q[i].y) - query(q[i].x - 1);
      if (q[i].k <= t)
        q1[++cnt1] = q[i];
      else
        q[i].k -= t, q2[++cnt2] = q[i];
    } else
      // update: update Fenwick Tree & classify
      if (q[i].y <= m)
        add(q[i].x, q[i].k), q1[++cnt1] = q[i];
      else
        q2[++cnt2] = q[i];
  for (int i = 1; i <= cnt1; i++)
    if (q1[i].type == 0) add(q1[i].x, -q1[i].k);  // clear Fenwick Tree
  for (int i = 1; i <= cnt1; i++) q[L + i - 1] = q1[i];
  for (int i = 1; i <= cnt2; i++)
    q[L + cnt1 + i - 1] = q2[i];  // merge temporary arrays back
  solve(l, m, L, L + cnt1 - 1), solve(m + 1, r, L + cnt1, R);
  return;
}

Optimization for static sequences

Problem 5 【Template】Persistent Segment Tree 2 Given a static sequence, answer queries for the \(k\)-th smallest in a subarray.

Both tree-of-trees and parallel binary search for the dynamic version have complexity \(O(n \log^2 n)\), but the static version can be solved with a persistent segment tree in \(O(n \log n)\). However, most parallel binary search implementations for the static version still run in \(O(n \log^2 n)\), risking TLE on large data. (Here we assume the value range is of the same order as the sequence length; if not, discretization can be applied.)

Optimization

  1. For each round of splitting, if there are \(t\) numbers \(\le mid\) in the current sequence, then for queries that go to the right group, we actually ask for the \((k - t)\)-th smallest. Therefore, we modify the query when it goes right. If the original answer value range is \([L,R]\), and the current split's answer range is \([l,r]\), then for queries participating in this split, the effect of all values in \([L,l)\) has already been removed earlier.
  2. Because each split should only depend on the current answer range \([l,r]\), the Fenwick Tree needs to be loaded and cleared many times.

What if the split does not depend solely on the current answer range?

This leads to an optimization that relates to the global sequence: maintain a pointer \(pos\) that tracks the current \(mid\) (the split center). Keep all elements \(\le pos\) set to \(1\) in the Fenwick Tree (others 0). Before each split, move \(pos\) and update the Fenwick Tree accordingly. The pointer moves \(O(n \log n)\) times. During splitting, for each query, compute the sum over its interval from the Fenwick Tree; if the condition holds, send it left; otherwise, right, without modifying the query.

Because we need to track the split center, we must update the Fenwick Tree accurately as \(pos\) moves. Before starting parallel binary search, sort the sequence by value and record each element's position; when moving \(pos\), modify the Fenwick Tree at that position. For most problems solvable by parallel binary search without modifications, this optimization can be applied to drastically reduce the number of data structure operations.

Since many load/clear operations of the Fenwick Tree are avoided, applying this optimization usually significantly improves the efficiency of parallel binary search (even if only by a constant factor). For the static k-th smallest query, the efficiency is not worse than the asymptotically better persistent segment tree. Notably, there exists an \(O(n \log n)\) parallel binary search implementation for the static problem.

Key part of reference code:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct Query {
  int i, l, r, k;
};  // the i-th query asks for k-th smallest in [l,r]

Query s[200005], t1[200005], t2[200005];
int n, m, cnt, pos, p[200005], ans[200005];
pair<int, int> a[200005];

void add(int x, int y);  // Fenwick Tree: add y at position x
int sum(int x);          // Fenwick Tree: prefix sum up to x

// current queries are [l,r], answer value range is [ql,qr]
void overall_binary(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (int i = l; i <= r; i++) ans[s[i].i] = ql;
    return;
  }
  int cnt1 = 0, cnt2 = 0, mid = (ql + qr) >> 1;
  // track split center: assume values in [1,pos] are already in Fenwick Tree
  while (pos <= n - 1 && a[pos + 1].first <= mid)
    add(a[pos + 1].second, 1), ++pos;
  while (pos >= 1 && a[pos].first > mid) add(a[pos].second, -1), --pos;

  for (int i = l; i <= r; i++) {
    int now = sum(s[i].r) - sum(s[i].l - 1);
    if (s[i].k <= now)
      t1[++cnt1] = s[i];
    else
      t2[++cnt2] = s[i];  // note: do not modify query info
  }
  for (int i = 1; i <= cnt1; i++) s[l + i - 1] = t1[i];
  for (int i = 1; i <= cnt2; i++) s[l + cnt1 + i - 1] = t2[i];

  overall_binary(l, l + cnt1 - 1, ql, mid);
  overall_binary(l + cnt1, r, mid + 1, qr);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
    p[++cnt] = a[i].first;
  }
  sort(a + 1, a + n + 1);  // sort sequence for discretization
  sort(p + 1, p + n + 1);
  cnt = unique(p + 1, p + n + 1) - p - 1;
  for (int i = 1; i <= n; i++)
    a[i].first = lower_bound(p + 1, p + cnt + 1, a[i].first) - p;
  // reading queries omitted
  overall_binary(1, m, 1, cnt);
  for (int i = 1; i <= n; i++) printf("%d\n", p[ans[i]]);
  return 0;
}

Predecessor and Successor in a subarray

Problem 6 Given a sequence, answer multiple queries for the predecessor (largest number strictly less than \(k\)) or successor (smallest number strictly greater than \(k\)) in a given subarray, assuming such numbers exist.

Take predecessor as example. A common data‑structure approach is first to count how many numbers in the interval are strictly less than \(k\) (say \(x\)), then query the \(x\)-th smallest number in the interval. For successor, count how many numbers are \(\le k\) (say \(x\)), then query the \((x+1)\)-th smallest number.

Consider using parallel binary search: parallel binary search is an efficient offline algorithm for the k-th smallest query, and CDQ divide‑and‑conquer can efficiently compute the rank in a subarray offline. First run CDQ divide‑and‑conquer to obtain the rank, then use parallel binary search to get the predecessor/successor.

This problem can also be solved offline with CDQ divide‑and‑conquer combined with a segment tree, but that is far less efficient than running CDQ divide‑and‑conquer + parallel binary search twice.

Constructing a non-decreasing sequence

Problem 7 Sequence Given a sequence, each operation can increase or decrease a number by \(1\). We want to transform the sequence into a non‑decreasing one, and the final sequence may only contain numbers that originally existed. Output the minimum number of operations.

This kind of problem can also be solved with dynamic programming or a greedy with undo.

Under the condition of minimizing operations, there must exist a solution where every number in the final sequence is one that originally existed (provable by induction). Since the problem does not require the final sequence, it reduces to finding the minimum operation count.

Because the final sequence must be non‑decreasing, we can use parallel binary search. Each round of parallel binary search decides the value range \([l,r]\) for the final sequence, while the answer value range is \([ql,qr]\). Let \(mid=\lfloor\frac{ql + qr}{2}\rfloor\). At the start of each round, assume all numbers go to \([mid+1,qr]\) (set the count of numbers going to \([ql,mid]\) to \(0\)). The initial cost is the number of operations needed to set the whole interval \([l,r]\) to \(mid+1\). Then iterate over positions \(i\) in \([l,r]\) and compute the cost of setting \([l,i]\) to \(mid\) and \([i+1,r]\) to \(mid+1\); if better than the current best, update the minimum cost and the number of elements that should go to \([ql,mid]\).

The splitting already ensures the final sequence's monotonicity is not broken, and because we always choose the minimum operation count, the final sequence obtained by parallel binary search must be non‑decreasing and have minimal operations. Output the computed operation count.

Key part of reference code:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[500005], ans[500005];  // a: original, ans: constructed

void overall_binary(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (int i = l; i <= r; i++) ans[i] = ql;
    return;
  }
  int cnt = 0,
      mid = ql + ((qr - ql) >> 1);  // initially all set to mid+1 (all go right)
  long long res = 0ll, sum = 0ll;
  for (int i = l; i <= r; i++) sum += abs(a[i] - (mid + 1));
  res = sum;
  for (int i = l; i <= r;
       i++) {  // try making [l,i] become mid (go left)
    sum -= abs(a[i] - (mid + 1));
    sum += abs(a[i] - mid);
    if (sum < res) cnt = i - l + 1, res = sum;  // found better, update
  }
  overall_binary(l, l + cnt - 1, ql, mid);
  overall_binary(l + cnt, r, mid + 1, qr);
}

Practice Problems

References

  • Fio's "A Brief Discussion on Several Non‑Classical Solutions for Data Structure Problems".
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用