Binary lifting is the standard technique for -th successor queries. When you see large and multiple queries, think powers of . It is a pattern you will use often. The preprocessing table can be large: space. Make sure you have enough memory.
For , you need about rows, which is manageable. Bit manipulation makes the query phase clean. Checking each bit of directly corresponds to the binary decomposition. Use bitwise AND to test bits.