Little Y's Segment Tree: Predecessor Chains and Binary Lifting¶
alternative-binary-lifting.cpp preprocesses the sequence, then answers each query as it is read without storing the entire query list. It supports the full constraints.
Read the final stack from right to left¶
The final interval position \(r\) always remains at the top. Immediately below it is the nearest earlier position whose value is strictly greater than \(a_r\) : every later intervening value is removed by \(a_r\) . Applying the same rule repeatedly gives the whole stack.
Let \(p(i)\) be the nearest position left of \(i\) with \(a_{p(i)}>a_i\) , or zero if none exists. A decreasing monotone stack computes all predecessors in linear time: before handling \(a_i\) , pop every value at most \(a_i\) , and use the remaining top as \(p(i)\) .
The final stack of \([l,r]\) , from top to bottom, is consequently \(r,p(r),p(p(r)),\ldots\) , stopping before the next position becomes smaller than \(l\) . Every predecessor lies strictly left, so the chain is acyclic. Equal values are never predecessors.
Count with binary lifting¶
Precompute \(J_0(i)=p(i)\) and \(J_k(i)=J_{k-1}(J_{k-1}(i))\) , with \(J_k(0)=0\) . Thus \(J_k(i)\) is reached after \(2^k\) predecessor edges.
For a query, begin at \(r\) with answer one. Test \(k\) from largest to smallest. If \(J_k(r)\ge l\) , take the jump and add \(2^k\) to the answer. Positions decrease along the chain, so a jump whose endpoint remains in the interval has every intermediate position in the interval as well. Greedy binary jumps count exactly the chain nodes in the interval, proving correctness.
There are \(\lfloor\log_2N\rfloor+1\) levels. Preprocessing takes \(O(N\log N)\) time, each query takes \(O(\log N)\) , and space is \(O(N\log N)\) without an \(O(M)\) query store. Compared with the reference method, the larger preprocessing table supports answering queries individually in input order. GPT-6 applies classical predecessor chains and binary lifting, supplies the proof and implementation, and validates them against direct simulation and formal data. See the measurements.