Max-Query 1 (Segment Trees)

#1

Please can you tell why my code is giving TLE?

#2

@Anshit,
Imagine a query(l,r) s.t tree[ind]<k for all ind, thus you query function will go till all the leaves, just to return 0, giving a complexity of O(nlogn).
Try thinking of binary search on segments.

#3

If i try to keep the track of the max value then?
like this


why is it still giving tle?

#4

@Anshit,
The case when tree[index].second > k, you will again traverse all the leaves. Try to use binary search over segments. A merge sort tree is used to handle such queries.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.