The key observation for this problem is that given the fraction $\frac{a}{b}$ in lowest terms, $k+\frac{1}{\frac{a}{b}}$ will also be in lowest terms.

The proof is as follows. Simplifying the expression yields $k+\frac{b}{a}=\frac{ka+b}{a}$. Let us consider $gcd(ka+b,a)$. By the Euclidean algorithm, we know this equals $gcd(b,a)$, and as $\frac{a}{b}$ is in lowest terms, $gcd(ka+b,a)=gcd(b,a)=1$. QED

Thus if we represent the fraction $\frac{a}{b}$ as the matrix $\left[\begin{array}{c}a\\ b\end{array}\right]$, we can express $k+\frac{1}{\frac{a}{b}}$ as the matrix $\left[\begin{array}{cc}k& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]$.

For 10% of points, we can answer each query by multiplying together the corresponding matrices.

Time Complexity: $\mathcal{O}(NQ)$

For the remaining 90% of points, we can use a range tree and the associative property of matrix multiplication to obtain a solution in $\mathcal{O}(Q\log N)$.

Alternatively, we can use a technique similar to the idea of prefix sum arrays. Note that ${\left[\begin{array}{cc}k& 1\\ 1& 0\end{array}\right]}^{-1}=\left[\begin{array}{cc}0& 1\\ 1& -k\end{array}\right]$. We can precompute $\prod _{i=1}^k\left[\begin{array}{cc}{a}_i& 1\\ 1& 0\end{array}\right]$ and $\prod _{i=1}^k\left[\begin{array}{cc}0& 1\\ 1& -a_i\end{array}\right]$ for $k=1,2,\dots ,N$ in $\mathcal{O}(N)$, thus the product $\prod _{i=l}^{r-1}\left[\begin{array}{cc}{a}_i& 1\\ 1& 0\end{array}\right]$ can be found in $\mathcal{O}(1)$.

Time Complexity: $\mathcal{O}(N+Q)$

A final solution is as follows. We claim that for any continued fraction $${\displaystyle a_1+\frac{1}{a_2+\frac{1}{\ddots +\frac{1}{a_k+\frac{1}{x}}}}}$$ there exists $a,b,c,d$ such that $${\displaystyle a_1+\frac{1}{a_2+\frac{1}{\ddots +\frac{1}{a_k+\frac{1}{x}}}}=\frac{ax+b}{cx+d}.}$$

This is equivalent to the matrix solution, and the proof of correctness is left as an exercise for the reader.