Binary Lifting - Complexity

Binary lifting preprocessing takes $O(n \log n)$ time and space. You fill a table of $n$ rows and $\log n$ columns, where each entry takes $O(1)$. A single DFS computes all depths in $O(n)$ time. Each LCA query takes $O(\log n)$ time because you iterate through at most $\log n$ powers of $2$ twice: once to equalize depths, once to climb together.

For $q$ queries, total time is $O(n \log n + q \log n)$. Space is $O(n \log n)$ for the up table. This is fast enough for most competitive programming problems with $n, q \leq 2 \times 10^5$. The main bottleneck is the $\log n$ factor per query, which Euler tour + RMQ can eliminate.