hellodummy's blog

By hellodummy, 3 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Code For Reference

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) $$$