I have an array of integers and have q queries on it . The number of queries is large . Each query is of the form: x l r . We have to find the largest element smaller than x in the range [l,r]. How can we optimize it.
Thanks in advance.
You can use a segment tree whose each node is a sorted array. Each sorted array contains all the elements within that range. In other words, the segement should look like a tree used in merge sort. You can use TreeSet as the segment tree nodes, because you don’t really need repeating elements.
The tree should look like this:
Now for each query, climb up from the root as you do in a standard segment tree ((lg N) conplexity). Now, you have located the nodes, each of which is a sorted segment of the whole array. Run binary search in each of the segments (Another lg N). The largest of these is the answer. Total complexity for each query: O((lg N)^2)
By using TreeSet as the nodes, you eliminate any repeating elements. Also, you have inbuild methods to find largest number smaller than ‘x’ in logarithmic time.
2 Likes
The l=0 method needs thinking. I don’t know if it’s possible or not.
Also, I don’t know if my approach is the best. Maybe, it’s solvable in lg(N) time…
Meanwhile, you can go through segment trees in detail in GeeksForGeeks.
1 Like