The following is taken from cp-algorithms
copy-pasted-part starts:
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.
copy-pasted-part ends
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!
I guess you are just confused how the complexity is $$$\mathcal{O}(\log{}n)$$$ ,instead of $$$\mathcal{O}(({\log{}n})^2) $$$
First thing to note that is any range segment is covered by range size which are distinct powers of 2, now lets say, for that particular power we need $$$\mathcal{O}(\log{}2^x) $$$ time as we are kinda binary searching on that segment, for all the powers we need is $$$\sum_{x}\mathcal{O}(\log{}2^x)$$$ , now you know that $$$ \sum_{i=0}^k 2^i = 2^{k+1} - 1$$$ .
Hence the complexity is $$$\mathcal{O}(\log{}2^{x+1}) $$$ which is equal to $$$\mathcal{O}(\log{}N) $$$