First, let us observe the steps to find \(X\).
The \(m\) in step 2 is the point that divides \([l,r]\) in the ratio \(b_j : a_j\) rounded down to an integer. If \(m\) equals \(i\), then \(x_i\) is the number of iterations so far; otherwise, we cut \([l,r]\) at \(m\) into two parts, and the part that contains \(i\) becomes the new \([l,r]\). Here, since \(\max (\frac{a_i}{b_i}, \frac{b_i}{a_i})\leq 2\), the length of the new segment is at most \(\lceil \frac{2}{3}\rceil\) of the length of the old segment, so the number of iterations is \(\mathrm{O}(\log N)\).

Let us determine the binary tree corresponding to \([l,r]\) that appears in the process of finding \(X\), as follows.

• The index of the root is the \(m\) for \([l,r]\), and the subtrees rooted at the left and right children are the binary trees corresponding to \([l,m-1]\) and \([m+1,r]\), respectively. (If the segment is empty, the tree has no children.)

This is the in-order numbering of vertices, and \(x_i\) is the depth of the vertex \(i\) corresponding to \([1,N]\). Thus, \(x_i-x_{i+1}\) is the absolute difference of the depths of vertex \(i\) and vertex \(i+1\), which is simply the distance between those vertices since, for two vertices with adjacent indices in the in-order numbering, one of them is an ancestor of the other. Therefore, the sought value is the length of the path visiting \(c_i,c_i+1,\ldots,d_i\) in this order.
Let \(T\) be the minimum Steiner tree for vertices with indices between \(c_i\) and \(d_i\), inclusive. Additionally, let \(r\) be the point with the smallest depth (the least common ancestor of \(c_i\) and \(d_i\) in the original tree). The process of starting at \(r\), visiting \(c_i,c_i+1,\ldots,d_i\), and returning to \(r\) is equivalent to performing DFS on \(T\), and the length of this path is twice the number of edges (the number of vertices minus one). The answer to the original question can be found by subtracting from this value the distance between \(c_i\) and \(d_i\), so the question can be solved by finding the number of vertices and the distance between \(c_i\) and \(d_i\). To simplify the computation of the number of vertices of \(T\), note that the set of vertices of \(T\) is the union of these sets: the set of vertices with indices between \(c_i\) and \(d_i\), and the set of vertices along the path between \(c_i\) and \(d_i\) with indices less than \(c_i\) or greater than \(d_i\).
Here is a specific way to find them. First, get to the least common ancestor \(r\) of \(c_i\) and \(d_i\) by DFS (if \(c_i\) and \(d_i\) are both less than \(m\), go to the left child; if both are greater than \(m\), go to the right child). Then, trace the path from \(r\) to \(c_i\) and to \(d_i\) independently. As mentioned above, the number of vertices of \(T\) can be found from the indices of the vertices on the \(c_i,d_i\)-path, and the distance can be found as \(x_{c_i} + x_{d_i} - 2x_{r}\). As mentioned in the beginning, the number of iterations is \(\mathrm{O}(\log N)\), and so is the depth of the binary tree. Therefore, the number of steps in this algorithm is also \(\mathrm{O}( \log N)\).