### hellodummy's blog

By hellodummy, 7 weeks ago,

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

 » 7 weeks ago, # |   +3 Code For Referenceint get_first(int v, int lv, int rv, int l, int r, int x) { if(lv > r || rv < l) return -1; if(l <= lv && rv <= r) { if(t[v] <= x) return -1; while(lv != rv) { int mid = lv + (rv-lv)/2; if(t[2*v] > x) { v = 2*v; rv = mid; }else { v = 2*v+1; lv = mid+1; } } return lv; } int mid = lv + (rv-lv)/2; int rs = get_first(2*v, lv, mid, l, r, x); if(rs != -1) return rs; return get_first(2*v+1, mid+1, rv, l ,r, x); } 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)$