Euler Tour + RMQ - Complexity

Euler tour construction: $O(n)$ time because you visit each edge exactly twice (once down, once up). Sparse table construction: $O(n \log n)$ time and space because the table has $n$ rows and $\log n$ columns, and each cell takes $O(1)$ to fill. Query: $O(1)$ time because you look up two precomputed values in the sparse table.

Total: $O(n \log n)$ preprocessing, $O(1)$ per query, $O(n \log n)$ space. For $q$ queries, total time is $O(n \log n + q)$. Compare this to binary lifting: $O(n \log n + q \log n)$. The difference matters when $q$ is large.