Skip to content

Binary Lifting

This page briefly introduces binary lifting.

Definition

Binary lifting works by repeated doubling. When a recurrence has a large state space, computing it linearly, one state after another, is too slow and uses too much memory. Instead, we let the step grow geometrically and compute only the values at positions that are integer powers of \(k\), which serve as representatives. When we need the value at another position, we assemble it from the representatives already computed, using the fact that any integer can be written as a sum of powers of \(k\). Binary lifting therefore also requires that the state space of the recurrence can be partitioned along powers of \(k\). Usually \(k\) is \(2\).1

Many algorithms use this technique; its most common applications are RMQ and finding the lowest common ancestor (LCA).

Applications

The RMQ problem

See the RMQ topic page.

RMQ stands for Range Maximum/Minimum Query: finding the maximum (or minimum) over a range. The sparse table solves RMQ by binary lifting.

LCA by binary lifting on trees

See Lowest Common Ancestor.

Example problems

Problem 1

Example

How do you measure every weight in \([0,31]\) with as few weights as possible? (The weights may go on only one pan of the balance.)

Approach

Use the five weights 1, 2, 4, 8, 16: they measure every weight in \([0,31]\). Likewise, the seven weights 1, 2, 4, 8, 16, 32, 64 measure every weight in \([0,127]\). If the weights are always nonnegative integer powers of 2, very few of them are enough to measure any weight we need.

For example, 10 weights are enough for every weight in \([0,1023]\), and 20 for every weight in \([0,1048575]\). Doubling the target weight costs only 1 more weight. This is called logarithmic growth, because the number of weights needed is proportional to the logarithm of the range of target weights.

Problem 2

Example

You are given a cycle of \(n\) vertices and a constant \(k\). A jump takes you from vertex \(i\) to vertex \((i+k)\bmod n+1\), and you make \(m\) jumps in total. Each vertex has a weight, denoted \(a_i\). Find the sum of the weights of the vertices that the \(m\) jumps start from, modulo \(10^9+7\).

Constraints: \(1\leq n\leq 10^6\), \(1\leq m\leq 10^{18}\), \(1\leq k\leq n\), \(0\le a_i\le 10^9\).

Approach

Simulating all \(m\) jumps by brute force is clearly out of the question: \(m\) can be as large as \(10^{18}\), so the simulation would take far too long.

So we need to preprocess: combine some information in advance so that a query can be answered quickly. Storing the result for every possible number of jumps would cost too much time and too much memory.

What should we precompute, then? Look at the first example again. Does it give you an idea?

Back to this problem. We want to precompute some information and then combine it into the answer as quickly as possible, but we cannot afford to precompute too much. So we precompute the information for jumps whose lengths are nonnegative integer powers of 2: there is little to precompute, and little to combine at query time.

Concretely, for every vertex we precompute the result of jumping 1, 2, 4, 8, ... steps from it: the vertex we land on and the sum of the vertex weights on the way. To jump 13 steps, we jump 1+4+8 steps: 1 step from the starting vertex, then 4 steps from where we landed, then 8 more. Adding up the precomputed sums along the way gives the sum of the vertex weights over the 13 steps.

For the \(2^i\) steps starting at each vertex, we store go[i][x], the vertex reached after \(2^i\) steps from vertex \(x\), and sum[i][x], the sum of the vertex weights collected over \(2^i\) steps from vertex \(x\). Two nested loops fill the tables. A jump of \(2^i\) steps is a jump of \(2^{i-1}\) steps followed by another of \(2^{i-1}\) steps, since \(2^{i-1}+2^{i-1}=2^i\). Hence sum[i][x] = sum[i-1][x]+sum[i-1][go[i-1][x]] and go[i][x] = go[i-1][go[i-1][x]].

A few implementation details need care. To count every vertex exactly once, we usually store the sums over half-open ranges: for a jump of 1 step we record only the weight of the starting vertex, and for a jump of 2 steps only the weights of the starting vertex and the next one. In other words, the vertex a jump lands on never contributes to sum. The sums of the two halves can then simply be added during preprocessing, without counting the end of the first half and the start of the second half twice.

The bound \(m\leq 10^{18}\) looks scary, but precomputing levels \(0\) through \(59\) is enough to solve the problem comfortably, far faster than brute-force enumeration. In the jargon, this solution has time complexity \(\Theta(n\log m)\) for preprocessing and \(\Theta(\log m)\) per query.

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
#include <cstdio>
using namespace std;

constexpr int mod = 1000000007;

int modadd(int a, int b) {
  if (a + b >= mod) return a + b - mod;  // subtract instead of taking the remainder: faster
  return a + b;
}

int vi[1000005];

int go[60][1000005];  // slightly oversized to avoid out-of-bounds access; put the smaller dimension first when you can
int sum[60][1000005];

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", vi + i);
  }

  for (int i = 1; i <= n; ++i) {
    go[0][i] = (i + k) % n + 1;
    sum[0][i] = vi[i];
  }

  // m <= 10^18, so levels 0..59 are enough
  for (int i = 1; i < 60; ++i) {
    for (int j = 1; j <= n; ++j) {
      go[i][j] = go[i - 1][go[i - 1][j]];
      sum[i][j] = modadd(sum[i - 1][j], sum[i - 1][go[i - 1][j]]);
    }
  }

  long long m;
  scanf("%lld", &m);

  int ans = 0;
  int curx = 1;
  for (int i = 0; m; ++i) {
    if (m & (1ll << i)) {  // is bit i of m set? (see bitwise operations)
      ans = modadd(ans, sum[i][curx]);
      curx = go[i][curx];
      m ^= 1ll << i;  // clear bit i
    }
  }

  printf("%d\n", ans);
}

References and notes


  1. From Yudong Li, Advanced Guide to Algorithm Contests (in Chinese), section 0x06, "Binary lifting". ↩