Skip to content

Parallel Binary Search

Introduction

In OI contests, some problems can be solved by binary search. When such a problem has many queries, though, running a separate binary search for each one may get TLE, and this is where parallel binary search comes in. Its main idea is to solve many queries together. (It is therefore an offline algorithm.)

A problem that parallel binary search can solve must have the following properties1:

  1. The answer to a query can be found by binary search.
  2. Updates contribute independently to checking an answer; no update changes the effect of another.
  3. If an update contributes to the check, its contribution is a fixed value that does not depend on the criterion being checked.
  4. Contributions are commutative, associative and additive.
  5. The problem allows an offline algorithm.

Explanation

Let \([l,r]\) be the value range of the answer and \([L,R]\) its domain. (That is, when computing answers we consider only the operations and queries whose indices lie in the range \([L,R]\), and the answers to these queries lie in \([l,r]\).)

  • First store all operations in an array in chronological order, then start the divide and conquer.
  • At each level of the divide and conquer, use a data structure (usually a Fenwick tree) to work out how the answer to each current query compares with \(mid\).
  • According to that comparison (at most \(mid\), or greater than \(mid\)), split the sequence of operations being processed into two parts, \(q1\) and \(q2\), and recurse on each.
  • When \(l=r\), the answer has been found: record it and return.

Note that while the value range being processed is \([l,r]\), any query whose final answer lies outside \([l,r]\) is handled at some other point of the parallel binary search.

Procedure

Note
  1. For readability, the code in this article is not always written the way it usually is in contests.
  2. If a piece of code is hard to follow, read the explanations of the earlier problems first: to save space, nothing is explained twice.

We start from ordinary binary search.

Global k-th smallest

Problem 1

Find the \(k\)-th smallest number in a sequence.

Solution

You could of course just sort. But what if we use binary search? Record in a data structure how many numbers fall in each range of values, then guess by binary search and check each guess against the data structure.

Problem 2

Answer many queries for the \(k\)-th smallest number in a sequence.

Solution

We could run one binary search per query. But we can also binary search for all the queries together.

Consider first what binary search really is. Suppose we have to guess a number in \([l,r]\), and after each guess we learn whether it was too large, too small or exactly right. We could try every value from \(l\) to \(r\), but binary search is better: guess that the answer is \(m = \lfloor\frac{l + r}{2}\rfloor\), check whether \(m\) is right, and adjust the bounds. Each query then costs \(O(\log n)\), so \(q\) queries take \(O(q\log n)\) time.

Now return to the problem. For all the current queries at once, guess that every answer is \(mid\), then check for each query in turn whether its answer is at most \(mid\) or greater than \(mid\). This splits the queries into two parts (not greater / greater), and we continue the binary search on each part. Note that if the answer to a query is greater than \(mid\), its \(k\) has to be updated before the query is moved to the right: if \(t\) numbers of the current sequence are less than or equal to \(mid\), then after the split the query really asks for the (\(k - t\))-th smallest number in the right range. When a part reaches \(l = r\), its binary search ends. As in a segment tree, each round splits the whole range \([1,n]\) in which the answers can lie (we assume coordinate compression has been done) into a number of parts. There are \(O(\log n)\) such rounds, and each round goes over the whole sequence of operations once. If going over the whole sequence and answering the corresponding queries takes \(O(T)\) time, parallel binary search runs in \(O(T\log n)\).

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
struct Query {
  int id, k;  // the index of this query, the k of this query
};

int ans[N], a[N];  // ans[i] is the answer to query i, a is the original sequence
int val[N], cnt[N];  // after coordinate compression: each value and its count (assumed already computed)

// returns how many numbers of the original sequence have a value 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;
}

Range k-th smallest

Problem 3

Answer many queries for the \(k\)-th smallest number in a range of a sequence.

Solution

Now every query comes with a range, and binary searching as before would make the check function far too slow. We still compare each query with the midpoint \(m\) of the value range: if \(t\) numbers in the query range are less than or equal to \(m\) and the query asks for the \(k\)-th smallest number in the range, then the answer is at most \(m\) when \(k \leq t\), and greater than \(m\) otherwise. (Watch the boundary cases.) So we need the number of elements of a range that are at most a given value. This is point addition with range sum queries, which a Fenwick tree handles quickly. For efficiency, count only the numbers of the sequence whose value lies in the value range \([l,r]\): before recursing further, split not only the queries but also the numbers being processed into two halves by value.

Reference code (key parts)
 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;
};  // the number at position p of the sequence has value x

struct Query {
  int l, r, k, id;
};  // the query with index id, asking for the k-th smallest number 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: sum over [1,p]
void clear();            // Fenwick tree: clear

void solve(int l, int r, vector<Num> a, vector<Query> q)
// a holds the numbers of the given sequence whose value lies in the value range [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 solution to [Template] Persistent Segment Tree 2 by parallel binary search, written in a more contest-like style.

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';
}

Range k-th smallest with updates

Problem 4 (Dynamic Rankings)

Given a sequence, support point updates and queries for the \(k\)-th smallest number in a range.

Solution

An update is simply the deletion of one number from the sequence followed by the addition of another. For convenience, we call queries and updates alike "operations". Later operations depend on earlier ones, so we cannot separate the counting from the handling of the queries as in Problem 3. Instead, store all the operations in one array, tag each with its type, and process them in order. To make the Fenwick tree easier to handle, split each update into an erase operation and an insert operation.

Optimizations

  1. Classifying the operations only ever changes their order, so we can work directly on the original array. Concretely, replace the arrays \(q\) and \(a\) that hold the operations during the binary search by one large global array, and let the recursion carry \(L\) and \(R\) instead: the range of the global array that holds the operations being processed. Record the current classification in temporary arrays, and write them back to the original array before recursing further.
  2. Clearing the whole Fenwick tree every time would blow up the running time. Instead, record the positions modified each time the Fenwick tree is used (the temporary arrays of item 1 already do this), and when the round is over add \(-1\) at those positions to reset the tree quickly.
  3. Initializing the sequence at the start reduces to insert operations.
Reference code (key parts)
 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 left and right ends of the range, and the k-th smallest is asked for
  // for an update, type = 0; x is the position updated, y is the value after the update,
  // and k says whether this operation is an insertion (1) or an erasure (-1); it is used when updating the Fenwick tree.
  // id is the original index of the operation, because the binary search scrambles the order of the operations
};

Opt q[N], q1[N], q2[N];
// q holds all the operations;
// during the binary search, operations sent to the left are stored in q1 and those sent to the right in q2.
int ans[N];
void add(int p, int x);
int query(int p);  // Fenwick tree functions, as in Problem 3

void solve(int l, int r, int L, int R)
// the current value range is [l,r], and the operations being processed are the range [L,R]
{
  if (l > r || L > R) return;
  int cnt1 = 0, cnt2 = 0, m = (l + r) / 2;
  // cnt1, cnt2: the number of operations sent to the left and to the 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) {  // a query: classify it
      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
      // an update: update the Fenwick tree & classify it
      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 the 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 the elements of the temporary arrays back into the original array
  solve(l, m, L, L + cnt1 - 1), solve(m + 1, r, L + cnt1, R);
  return;
}

An optimization for static sequences

Problem 5 ([Template] Persistent Segment Tree 2)

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

Solution

Nested trees and parallel binary search both solve range \(k\)-th smallest with updates in \(O(n \log^2 n)\). The static problem, however, can be solved in \(O(n \log n)\) time with a persistent segment tree, whereas almost every parallel binary search solution to static range \(k\)-th smallest runs in \(O(n \log^2 n)\) and risks TLE when the constraints are large. (We assume here that the value range is of the same order of magnitude as the length of the sequence; when it is not, coordinate compression reduces the problem to that case.)

Optimization

  1. In every round of partitioning, if \(t\) numbers of the current sequence are less than or equal to \(mid\), a query sent to the right range really asks for the (\(k - t\))-th smallest number there, so the queries sent to the right range are modified. If the original value range of the answer is \([L,R]\) and the value range of the answer in some round is \([l,r]\), then for the queries taking part in that round the effect of every value in \([L,l)\) has already been removed.
  2. Every round has to depend only on the current value range \([l,r]\) of the answer, so the Fenwick tree must be loaded and cleared many times.

What if a round did not depend only on the current value range of the answer?

This leads to an optimization that works with the whole sequence. Maintain a pointer \(pos\) that tracks the \(mid\) of each round (the midpoint of the divide and conquer): the indices of all elements \(\leq pos\) are set to \(1\) in the Fenwick tree, and every other position of the tree is set to \(0\). Before each round, move \(pos\) and update the Fenwick tree. The number of times \(pos\) moves is of the same order of magnitude as \(n \log n\). In a round, query the Fenwick tree over the range of each query; a query that meets the condition goes to the left range and any other goes to the right range, and the queries do not have to be modified.

To track the midpoint, \(pos\) has to update the Fenwick tree exactly. Before the parallel binary search, sort the sequence by value and record the index of each element; as the pointer moves, update the Fenwick tree at the corresponding indices. This optimization applies to the vast majority of problems that can be solved by parallel binary search and have no updates, and it greatly reduces the number of operations on the data structure.

Because it saves so much loading and clearing of the Fenwick tree, this optimization usually makes parallel binary search noticeably faster (even though it only improves the constant factor). On static range \(k\)-th smallest it is every bit as fast as the persistent segment tree, whose time complexity is better. Note also that static range \(k\)-th smallest has a parallel binary search implementation that runs in \(O(n \log n)\).

Reference code (key parts)
 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 the k-th smallest value in the range [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 over [1,x]

// the queries being processed are [l,r], the value range of the answer 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 the midpoint; the values of [1,pos] are taken to be loaded into the 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: the query must not be modified
  }
  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 the sequence; coordinate compression
  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 the queries is 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 range

Problem 6

Answer many queries on a sequence for the predecessor of \(k\) in a range (the largest number strictly less than \(k\)) or its successor (the smallest number strictly greater than \(k\)). Such a number is guaranteed to exist.

Solution

Take the predecessor. The usual data structure solution first counts the numbers in the range that are strictly less than \(k\) (say there are \(x\) of them) and then queries the \(x\)-th smallest number in the range. For the successor, count the numbers in the range that are not greater than \(k\) (again \(x\) of them) and then query the (\(x+1\))-th smallest number in the range.

Now let us solve the problem with parallel binary search. Parallel binary search is an efficient offline algorithm for range \(k\)-th smallest, and CDQ divide and conquer computes ranks within a range efficiently offline. Run CDQ divide and conquer once to obtain the ranks, and parallel binary search then gives the predecessor and the successor within the range.

The problem can also be solved offline in a single pass by CDQ divide and conquer with a nested segment tree, but that is far slower than the two passes of CDQ divide and conquer plus parallel binary search.

Constructing a monotone sequence

Problem 7 (Sequence)

Given a sequence, one operation changes some number by \(+1\) or \(−1\). The sequence must become non-decreasing, and the resulting sequence may contain only numbers that occurred before the changes. Output the minimum number of operations.

Solution

Problems of this kind can also be solved by dynamic programming or by greedy with undo.

Among the solutions that minimize the number of operations, there is always one in which every number of the final sequence already occurred in the sequence before the changes. This can be proved by mathematical induction. The problem does not ask for the final sequence, so it reduces to finding the minimum number of operations.

The final sequence must be non-decreasing, so parallel binary search applies. Each round decides the values of the final sequence on a range \([l,r]\) of positions, for which the value range of the answer is \([ql,qr]\). Let \(mid=\lfloor\frac{ql + qr}{2}\rfloor\). At the start of a round, all the numbers are assigned to \([mid+1,qr]\) by default (\(0\) numbers go to \([ql,mid]\)), and the initial cost is the number of operations needed to set the whole range \([l,r]\) to \(mid+1\). Then enumerate the positions \(i\) of \([l,r]\) in order and compute the total number of operations needed to set \([l,i]\) to \(mid\) and \([i+1,r]\) to \(mid+1\). Whenever this beats the best number so far, update the minimum number of operations and the count of numbers that go to \([ql,mid]\).

The partition never breaks the monotonicity of the final sequence. And because each round takes the minimum number of operations, \(mid\) is always a better value than \(mid+1\) for the numbers that end up in the left range. So the sequence that parallel binary search produces is non-decreasing and uses the minimum number of operations. Compute that number and output it.

Reference code (key parts)
 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: the original sequence, ans: the constructed sequence

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);  // by default everything starts as mid+1 and goes to the right range
  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 changing [l,i] from mid+1 to mid and sending it to the left range
    sum -= abs(a[i] - (mid + 1));
    sum += abs(a[i] - mid);
    if (sum < res) cnt = i - l + 1, res = sum;  // mid is better for [l,i]: update
  }
  overall_binary(l, l + cnt - 1, ql, mid);
  overall_binary(l + cnt, r, mid + 1, qr);
}

Practice problems

References and notes


  1. Haoran Xu. A Brief Discussion of Several Non-Classical Solutions to Data Structure Problems (in Chinese). Collected papers of the 2013 Chinese national team candidates for the Olympiad in Informatics. ↩