Parallel Binary Search

Given a sequence, query its $k$-th smallest number.

Of course, we can sort the sequence directly. What if we use binary search? We can use a data structure to record how many numbers fall into each size range, then make guesses with binary search and verify them using the data structure.

Given a sequence, answer multiple queries for its $k$-th smallest number.

We can perform one binary search for each query; however, we can also put all queries through binary search together.

First consider the essence of binary search: suppose we need to guess a number in $[l,r]$. After making a guess, we learn whether it is too large, too small, or exactly correct. We could of course enumerate from $l$ to $r$, but a better method is binary search: guess that the answer is $m = \lfloor\frac{l + r}{2}\rfloor$, verify whether $m$ is correct, and then adjust the bounds. This gives each query a complexity of $O(\log n)$; if the number of queries is $q$, the time complexity is $O(q\log n)$.

Returning to the current set of queries, we can guess that every query's answer is $mid$, then verify one by one whether each answer should be less than or equal to $mid$ or greater than $mid$, and divide the queries into two groups (not greater than / greater than), continuing the binary search for each group. Note that if a query's answer is greater than $mid$, its $k$ must be updated before it is assigned to the right side: if, for $mid$, the current sequence has $t$ numbers less than or equal to it, then after the query is divided, it is actually asking for the $k - t$-th smallest number in the right interval. If a group's $l = r$, the binary search for that group is finished. Using the relevant ideas from segment trees, each round divides the entire possible answer interval $[1,n]$ (assuming it has already been discretized) into several parts. There are $O(\log n)$ such divisions, and each division processes the entire operation sequence once. If processing the entire sequence and supporting the corresponding queries takes $O(T)$ time, the time complexity of parallel binary search is $O(T\log n)$.

struct Query {
  int id, k;  // the ID of this query, and its k
};

int ans[N], a[N];  // ans[i] is the answer to query i; a is the original sequence
int val[N], cnt[N];  // the corresponding values and their counts after discretization (assumed ready)

// Return the number of numbers in the original sequence whose values lie 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;
}

Given a sequence, answer multiple queries for the $k$-th smallest number in an interval.

When queries involve a specified interval, applying the previous binary-search method makes the time complexity of the check function explode. We still consider the relationship between the query and the value-domain midpoint $m$: if there are numbers no greater than $m$ in the query interval, with their count denoted by $t$, and the query asks for the $k$-th smallest number in that interval, then when $k \leq t$, the answer is no greater than $m$; otherwise, the answer is greater than $m$. (Pay attention to the boundary conditions.) Here we need to record the number of values in an interval that are less than or equal to a specified number; this is a point update plus a range-sum query, which can be handled efficiently with a Fenwick tree. For greater efficiency, we count only numbers in the sequence whose values lie in the value-domain interval $[l,r]$; that is, before recursing further, we divide not only the queries but also the currently processed numbers into two halves by value range.

struct Num {
  int p, x;
};  // the value x is at position p in the sequence

struct Query {
  int l, r, k, id;
};  // query number k-th smallest in [l,r], with ID id

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();            // clear the Fenwick tree

void solve(int l, int r, vector<Num> a, vector<Query> q)
// a contains the numbers in the given sequence whose values lie 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;
}

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

Given a sequence, support point updates and range $k$-th-smallest queries.

A point update can be understood directly as deleting one number from the original sequence and then adding another. For convenience, we call queries and updates collectively “operations.” Because later operations depend on earlier ones, unlike in Problem 3, we cannot separate counting from query processing; instead, we can store all operations in an array, distinguish their types with a flag, and process them in order. To make Fenwick-tree processing easier, an update can be split into an erase operation and an insertion operation.

Optimization

1. Notice that classifying operations only changes their order, so we can operate directly on the original array. Specifically, during binary search, replace the $q, a$ arrays that record operations with one large global array, and record $L, R$, meaning the interval of the global array containing the operations currently being processed. Use temporary arrays to record the current classification, then write the temporary arrays back to the original array before recursing further.
2. Clearing the Fenwick tree every time causes the time complexity to explode. We can record the positions modified during each use (the temporary arrays mentioned in point 1 already provide this information), and add $-1$ back at the original positions after the current operation to clear it quickly.
3. The initialization operations for the sequence at the beginning can be simplified into insertion operations.

struct Opt {
  int x, y, k, type, id;
  // For a query, type = 1; x and y are the left and right interval boundaries, and k is the k-th smallest queried
  // For an update, type = 0; x is the update position, and y is the value after the update,
  // k indicates whether the current operation is an insertion (1) or an erase (-1), and is used when updating the Fenwick tree.
  // id records the operation's original index, since the operation order is disrupted during binary search
};

Opt q[N], q1[N], q2[N];
// q contains all operations,
// during binary search, operations assigned to the left are stored in q1, and those assigned to the right are stored in q2.
int ans[N];
void add(int p, int x);
int query(int p);  // Fenwick-tree function; see Problem 3 for its meaning

void solve(int l, int r, int L, int R)
// the current value range is [l,r], and the operation interval being processed is [L,R]
{
  if (l > r || L > R) return;
  int cnt1 = 0, cnt2 = 0, m = (l + r) / 2;
  // cnt1 and cnt2 are the numbers of operations assigned to the left and right, respectively
  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 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
      // update: modify and classify in the Fenwick tree
      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 temporary arrays back into the original array
  solve(l, m, L, L + cnt1 - 1), solve(m + 1, r, L + cnt1, R);
  return;
}

Given a sequence, answer range $k$-th-smallest queries.

The tree-of-trees and parallel-binary-search solutions to the dynamic range $k$-th-smallest problem both have complexity $O(n \log^2 n)$. However, a static range $k$-th-smallest problem can be solved with a persistent segment tree in $O(n \log n)$ time, while the code for almost all parallel-binary-search solutions to the static range $k$-th-smallest problem has time complexity $O(n \log^2 n)$, which risks TLE on large data ranges. (Here it is assumed that the value range and sequence length have the same order of magnitude; if they do not, discretization can convert them to the same order.)

Optimization

1. In each round of partitioning, if, among the values no greater than $mid$, there are $t$ numbers, then after partitioning the queries are actually asking for the $k - t$-th smallest number in the right interval, so the queries assigned to the right interval are modified. If the original answer value range is $[L,R]$ and the answer value range in one partition is $[l,r]$, then for the queries participating in this partition, the influence of all values in $[L,l)$ has already been eliminated earlier.
2. Since each round of partitioning must depend only on the current answer value range $[l,r]$, the Fenwick tree must be loaded and cleared many times.

What if the partition did not depend only on the current answer value range?

This leads to an optimization method related to the global sequence: maintain a pointer $pos$ to track the $mid$ (divide-and-conquer center) of each partition, set the indices corresponding to all elements $\leq pos$ to $1$ in the Fenwick tree, and set all other positions to $0$. Move $pos$ and update the Fenwick tree before each partition. The number of moves of $pos$ has the same order as $n \log n$. During partitioning, query the value of the corresponding interval in the Fenwick tree for each query; if the condition holds, assign it to the left interval, otherwise assign it to the right interval. There is no need to modify the queries.

Since the divide-and-conquer center must be tracked, $pos$ must update the Fenwick tree accurately. Before parallel binary search, sort the sequence by element value and record the corresponding indices; when the pointer moves, make the corresponding updates to the indices in the Fenwick tree. For the vast majority of problems that can be solved with parallel binary search and have no updates, this optimization can be applied to greatly reduce the number of data-structure operations.

By eliminating many Fenwick-tree loading and clearing operations, this optimization usually improves the efficiency of parallel binary search noticeably (even if only as a constant-factor optimization). For the static range $k$-th-smallest problem, its efficiency is no worse than that of the persistent segment tree, whose time complexity is asymptotically better. It is worth noting that the static range $k$-th-smallest problem also has a parallel-binary-search implementation with time complexity $O(n \log n)$.

struct Query {
  int i, l, r, k;
};  // the i-th query asks for the k-th smallest value 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);  // add y at position x in the Fenwick tree
int sum(int x);          // prefix sum over [1,x] in the Fenwick tree

// the queries currently being processed are [l,r], and the 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 the divide-and-conquer center; assume the values in [1,pos] are already 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 that the query information 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 and discretize it
  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;
  // omit reading the queries
  overall_binary(1, m, 1, cnt);
  for (int i = 1; i <= n; i++) printf("%d\n", p[ans[i]]);
  return 0;
}

Given a sequence, answer multiple queries for the predecessor of $k$ in an interval (strictly less than $k$, and the largest such number) or its successor (strictly greater than $k$, and the smallest such number). It is guaranteed that such a number exists.

Taking the predecessor as an example, a typical data-structure solution first queries how many numbers in the interval are strictly less than $k$ (let their number be $x$), and then queries the $x$-th smallest number in the interval. For the successor, query how many numbers in the interval are less than or equal to $k$ (their number is $x$), and then query the $x+1$-th smallest number.

Consider using parallel binary search to solve this problem: parallel binary search is an efficient offline algorithm for finding the $k$-th smallest number in an interval, while CDQ divide and conquer can efficiently find interval ranks offline. Run CDQ divide and conquer once to obtain the ranks, and then use parallel binary search to obtain the predecessors and successors within the intervals.

This problem can also be solved offline in one pass with CDQ divide and conquer over a segment tree, but it is much less efficient than running CDQ divide and conquer twice followed by parallel binary search.

Given a sequence, each operation can change a number by $+1$ or $−1$. Make the sequence nondecreasing, with the restriction that the modified sequence may contain only values that appeared in the original sequence, and output the minimum number of operations.

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

Under the condition that the number of operations is minimized, there is always a solution in which every value in the final sequence appeared in the original sequence. This can be proved by mathematical induction. Since the problem does not require the final sequence itself, it becomes a problem of finding the minimum number of operations.

Because the final sequence must be nondecreasing, parallel binary search can be used. In each round, parallel binary search determines the value range $[l,r]$ of the final sequence; the answer value range at this point is $[ql,qr]$. Let $mid=\lfloor\frac{ql + qr}{2}\rfloor$. At the beginning of each binary-search round, assume that all numbers are assigned to $[mid+1,qr]$ (the number assigned to $[ql,mid]$ is set to $0$), and initialize the cost to the number of operations required to set the entire sequence interval $[l,r]$ to $mid+1$. Enumerate, in order, the numbers in $[l,r]$, denoting each by $i$, and calculate the sum of the operation counts for setting $[l,i]$ to $mid$ and $[i+1,r]$ to $mid+1$. If it is better than the previous operation count, update the minimum operation count and the number of numbers to assign to $[ql,mid]$.

The partitioning guarantees that the monotonicity of the final sequence is not broken. Moreover, because the minimum operation count is chosen each time, the numbers ultimately assigned to the left interval are guaranteed to do better with value $mid$ than with $mid+1$. Therefore, the sequence obtained by parallel binary search is nondecreasing and has the minimum number of operations. Compute and output the operation count.

int a[500005], ans[500005];  // a: original sequence; ans: 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);  // initially fill with mid+1 and assign everything to the right interval
  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 replacing mid+1 with mid for [l,i] and assigning it to the left interval
    sum -= abs(a[i] - (mid + 1));
    sum += abs(a[i] - mid);
    if (sum < res) cnt = i - l + 1, res = sum;  // [l,i] is better at mid; update
  }
  overall_binary(l, l + cnt - 1, ql, mid);
  overall_binary(l + cnt, r, mid + 1, qr);
}