Binary Lifting

Binary lifting (also known as doubling) is a technique that uses the idea of doubling – processing in steps of powers of 2 – to transform tasks that would normally require linear time into ones that run in logarithmic time. This significant reduction in time complexity has made binary lifting a popular tool in solving a variety of algorithmic problems.

Definition

Binary lifting is based on the insight of "doubling" the number of steps processed at once. By precomputing information for jumps of 1 step, 2 steps, 4 steps, 8 steps, and so on, many problems that naturally require iterating over a sequence of operations can instead be solved by combining a few of these precomputed results. As a result, operations that would have taken O(n) time may instead take O(log n) time.

This idea is especially effective in several classical algorithmic challenges.

Applications

Range Maximum/Minimum Query (RMQ)

RMQ stands for Range Maximum/Minimum Query. It asks you to quickly determine the maximum or minimum value in a subarray. One common method to solve RMQ using the doubling idea is by constructing a Sparse Table, which precomputes answers for ranges whose lengths are powers of two. This structure allows you to answer queries efficiently.

Computing Lowest Common Ancestors (LCA) in Trees

Binary lifting is frequently used in tree algorithms, particularly for determining the lowest common ancestor (LCA) of two nodes. By precomputing the ancestors for each node at distances of 2^0, 2^1, 2^2, and so on, one can rapidly "lift" nodes upward to find their LCA with logarithmic time complexity per query.

Example Problems

Example 1: Weighing with Minimal Weights

Imagine you need to measure every integer weight between 0 and 31 using a balance scale, but you are only allowed to place weights on one side of the scale. What is the smallest set of weights you can use?

The answer is to use weights of 1, 2, 4, 8, and 16. With just these five weights, you can measure any integer weight in the given range. The same idea extends naturally: to measure weights from 0 up to 127, you would use weights 1, 2, 4, 8, 16, 32, and 64. Notice that each weight is a power of 2.

Why is this so efficient? Because every time you double the range of weights you want to measure, you only need to add one more weight. This means that the number of weights required grows logarithmically with the maximum weight you wish to measure.

Example 2: Jumping on a Circular Array

Consider a circular array with n nodes, where each node i has an associated weight a_i. You are given a constant k; from any node i, you will jump to the node at position ((i + k) mod n). This process is repeated m times. Your goal is to compute the sum of the weights of the starting nodes of these jumps (taken in order) modulo $10^9+7$ .

The input limitations are very large:

1 ≤ n ≤ 10^6
1 ≤ m ≤ 10^18
1 ≤ k ≤ n
0 ≤ a_i ≤ 10^9

Because m can be extraordinarily large (up to 10^18), it is impossible to simulate each jump one by one. Instead, we use binary lifting to quickly compute the result of multiple jumps.

The Key Idea

Precompute two arrays for jumps in powers of two:

For each node, store where it lands after 2^i jumps.
Similarly, store the accumulated weight sum when making those 2^i jumps.

Let:

go[i][x] be the index of the node reached after making 2^i jumps starting from node x.
sum[i][x] be the sum of the weights encountered (using a left-closed, right-open convention to avoid double-counting the landing node’s weight) when making 2^i jumps from node x.

You can build these arrays recursively. Notice that a jump of 2^i steps can be broken into two consecutive jumps of length 2^(i-1):

go[i][x] = go[i-1][go[i-1][x]]

and

sum[i][x] = sum[i-1][x] + sum[i-1][go[i-1][x]]

After preprocessing, the answer to a query of m jumps can be constructed by decomposing m into a sum of powers of 2. For instance, to simulate 13 jumps, since 13 in binary is 1101, you combine results from jumps of 8, 4, and 1 step.

Now, let’s see how this approach can be implemented in Python.

mod = 10**9 + 7
 
def modadd(a, b):
    s = a + b
    if s >= mod:
        return s - mod
    return s
 
def main():
    import sys
    input_data = sys.stdin.read().strip().split()
    if not input_data:
        return
    it = iter(input_data)
    n = int(next(it))
    k = int(next(it))
    weights = [int(next(it)) for _ in range(n)]
    
    # Precompute the immediate jump destination and the initial sum (for jump length 1)
    go = []
    sum_list = []
    # For 1 jump (2^0), our arrays are 0-indexed.
    go0 = [ (i + k) % n for i in range(n) ]
    sum0 = weights[:]  # The sum for a single jump is just the weight of the starting node.
    go.append(go0)
    sum_list.append(sum0)
    
    # Determine maximum power needed.
    # m is the total number of jumps.
    m = int(next(it))
    max_power = m.bit_length()  # This will cover all bits required for m.
    
    # Precompute for each i up to max_power
    for i in range(1, max_power):
        go_prev = go[i-1]
        sum_prev = sum_list[i-1]
        curr_go = [0] * n
        curr_sum = [0] * n
        for x in range(n):
            nxt = go_prev[x]
            curr_go[x] = go_prev[nxt]
            curr_sum[x] = modadd(sum_prev[x], sum_prev[nxt])
        go.append(curr_go)
        sum_list.append(curr_sum)
    
    # Process m jumps using binary lifting
    ans = 0
    cur = 0  # Start at index 0 (the first node)
    bit = 0
    while m:
        if m & 1:
            ans = modadd(ans, sum_list[bit][cur])
            cur = go[bit][cur]
        m //= 2
        bit += 1
    
    sys.stdout.write(str(ans))
 
if __name__ == '__main__':
    main()

Explanation

We first read the number of nodes (n), the jump constant (k), and the weight for each node.
The arrays go[0] and sum_list[0] are initialized to represent the result of a single jump.
Next, for each power of 2 up to the maximum needed (derived from the binary length of m), we precompute where each node would land after 2^i jumps and the corresponding accumulated weight sum.
To answer the query for m jumps, we decompose m into its binary representation. For each bit that is set (meaning a jump segment corresponding to that power of 2 is needed), we update our answer and current position accordingly.
The process achieves a time complexity of O(n log m) during preprocessing and O(log m) per query, making it very efficient even for extremely large m.

This example highlights the strength of binary lifting in reducing what would be an infeasible number of operations to a manageable number by leveraging precomputed "jumps" and sums.

By mastering binary lifting, you can handle a range of algorithms that benefit greatly from its logarithmic time characteristic. Happy coding!

Time and Space Complexity Constructive Algorithms