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
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 | |
References and notes
-
From Yudong Li, Advanced Guide to Algorithm Contests (in Chinese), section 0x06, "Binary lifting". ↩
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Ir1d, ShadowsEpic, Fomalhauthmj, siger-young, MingqiHuang, Xeonacid, hsfzLZH1, orzAtalod, NachtgeistW, H-J-Granger, Chrogeek, 24OI-bot, PeterlitsZo, leoleoasd, Enter-tainer, Great-designer, Backl1ght, iamtwz, opsiff, CCXXXI, Tiphereth-A, yu-qe, HeRaNO, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.