Skip to content

Binary Lifting

This page briefly introduces the binary lifting method.

Definition

Binary lifting, as the name suggests, means "doubling". When performing recursion, if the state space is large, typical linear recursion may not meet the time and space complexity requirements. In such cases, we can use a doubling approach, only computing the values at positions that are integer powers of \(k\) in the state space as representatives. When the value at another position is needed, we use the property that "any integer can be expressed as the sum of several powers of \(k\)" to combine the previously computed representative values to obtain the required value. Therefore, using the binary lifting algorithm also requires that the state space of the recursion problem can be partitioned with respect to powers of \(k\). Typically, \(k\) is taken as \(2\).1

This method is applied in many algorithms, most commonly in RMQ problems and finding LCA (Lowest Common Ancestor).

Applications

RMQ Problem

See: RMQ Topic

RMQ stands for Range Maximum/Minimum Query. The method using binary lifting to solve RMQ problems is the Sparse Table.

Binary Lifting for LCA on Trees

See: Lowest Common Ancestor

Example Problems

Example 1

Example

How can we weigh all weights in the range \([0,31]\) using as few weights as possible? (Weights can only be placed on one side of the scale.)

Solution

The answer is to use the five weights 1, 2, 4, 8, 16, which can weigh all weights in \([0,31]\). Similarly, to weigh all weights in \([0,127]\), we can use the seven weights 1, 2, 4, 8, 16, 32, 64. Each time we choose weights that are powers of 2, we can use very few weights to measure any weight we need.

Why "very few"? Because if we want to measure all weights in \([0,1023]\), we only need 10 weights; for \([0,1048575]\), we only need 20. If our target weight range doubles, the number of weights only increases by 1. This is called "logarithmic" growth, because the number of weights required is proportional to the logarithm of the target weight range.

Example 2

Example

Given a ring of length \(n\) and a constant \(k\), each jump goes from point \(i\) to point \((i+k)\bmod n+1\), for a total of \(m\) jumps. Each point has a weight \(a_i\). Find the sum of the weights of the starting points of the \(m\) jumps, modulo \(10^9+7\).

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

Solution

Obviously, we cannot simulate \(m\) jumps directly here. Because \(m\) can be as large as \(10^{18}\), brute-force simulation would be too slow.

Therefore, some preprocessing is needed to integrate information in advance so that queries can be answered faster. However, recording the result for every possible number of jumps would be infeasible in both time and space.

So how should we preprocess? Look back at the first example. Do you have an idea now?

Back to this problem. We need to preprocess some information and then use it to efficiently compute the answer. At the same time, the preprocessed information should not be too large. So we can preprocess information in units of powers of 2. This way, only a small amount of information needs to be preprocessed, and integration is also straightforward.

For this problem, we preprocess the results (destination point and sum of weights) for jumps of 1, 2, 4, 8, etc. steps from each starting point. Then, to jump 13 steps, we only need to jump 1+4+8 steps. That is, first jump 1 step from the starting point, then jump 4 steps from the new point, then jump 8 steps, while accumulating the precomputed weight sums, to get the total weight sum for 13 jumps.

For each starting point and each \(2^i\) steps, we record go[i][x] as the destination after jumping \(2^i\) steps from point \(x\), and sum[i][x] as the sum of weights obtained after jumping \(2^i\) steps from point \(x\). During preprocessing, using a double loop, the information for jumping \(2^i\) steps can be seen as jumping \(2^{i-1}\) steps first, then another \(2^{i-1}\) steps, since clearly \(2^{i-1}+2^{i-1}=2^i\). That is, we have 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]].

Of course, some implementation details need attention. To avoid double-counting or missing counts, we typically preprocess "left-closed, right-open" weight sums. That is, for a jump of 1 step, we only record the weight of the starting point; for a jump of 2 steps, we only record the sum of the starting point and the next point. In other words, we never include the weight of the final destination in sum. This way, during preprocessing, we can simply add the two partial sums directly without worrying about the endpoint of the first segment and the starting point of the second segment being counted twice.

Although \(m\leq 10^{18}\) in this problem seems daunting, we only need to preprocess for \(i\) up to 65 to solve it easily, which is much faster than brute-force enumeration. In technical terms, the time complexity of this approach is \(\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;  // Use subtraction instead of modulo for speed
  return a + b;
}

int vi[1000005];

int go[75][1000005];  // Slightly enlarge the array to avoid out-of-bounds; put smaller dimension first
int sum[75][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];
  }

  int logn = 31 - __builtin_clz(n);  // A quick way to compute floor(log2(n))
  for (int i = 1; i <= logn; ++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)) {  // Check if the i-th bit of m is 1 (see bitwise operations)
      ans = modadd(ans, sum[i][curx]);
      curx = go[i][curx];
      m ^= 1ll << i;  // Clear the i-th bit
    }
  }

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

  1. Quoted from Li Yudong's "Advanced Guide to Algorithm Competitions", Section 0x06: Binary Lifting. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用