Core Idea - Binary Representation

Any number $k$ can be written as a sum of distinct powers of $2$. That is what binary representation means. For example, $13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$. If $k = 13 = 8 + 4 + 1$, you jump $8$ steps, then $4$, then $1$. Each jump is precomputed.

You combine precomputed results to get the final answer. This decomposition is unique and uses at most $\log k$ powers, giving you the logarithmic query time. Binary representation is what makes it work.