Query Example

Say $k = 13$ and you are at node $v$. Binary: $13 = 1101_2$. Bit $3$ is set: jump $2^3 = 8$ steps. Now v = up[v][3], $k = 5$. Bit $2$ is set: jump $2^2 = 4$ steps.

Now v = up[v][2], $k = 1$. Bit $0$ is set: jump $2^0 = 1$ step. Now v = up[v][0], $k = 0$. You have jumped $8 + 4 + 1 = 13$ steps in three jumps. Each jump uses one precomputed entry from the $up$ table, so no extra traversal is needed.