Complexity Summary

Preprocessing: $O(n \log n)$ time, $O(n \log n)$ space. You build the sparse table once. Queries: $O(\log k)$ per query, where $k$ is the jump distance. In the worst case, $k = n$, so queries take $O(\log n)$. If you have $q$ queries, total time is $O(n \log n + q \log n)$. For $n = 100,000$ and $q = 1,000,000$, that is under $20$ million operations.

This is fast enough for any competitive programming time limit.