The following is taken from cp-algorithms
The task is as follows: for a given value x and a range a[l…r] find the smallest i in the range a[l…r], such that a[i] is greater than x.
This task can be solved using binary search over max prefix queries with the Segment Tree. However, this will lead to a O(log2n) solution.
Instead, we can use the same idea as in the previous sections, and find the position by descending the tree: by moving each time to the left or the right, depending on the maximum value of the left child. Thus finding the answer in O(logn) time.
Here's the link: Link
I am not able to understand the implementation of this problem. Can anyone please help me?
Thank you so much!