Store a sorted array [L...R]  in each vertex of your ST,  corresponding to [L;R].

Hey!
Do you mind explaining the Segment tree approach a little bit more? I still couldn't understand

Hi
It is frequently called merge sort tree

So there is an array TRANSPORTED[i]
If we have want to find some value in interval of array cells from i=l to i=r
We can do binary search in sorted sequence TRANSPORTED[l], TRANSPORTED[l+1],... TRANSPORTED [r-1], TRANSPORTED[r]

In merge sort tree
We have some sorted subsequences precalculated
It is possible to represent any subsequence [l..r] as union of O(log(n)) such precalculated subsequences