In vector(sorted) when we want to find number of elements in range [l,r] we simple use upper_bound®- lower_bound(l), but it is not possible to use the same code in set or maps. I do not want to use vectors because there can be case of removing element from vector which O(n), whereas sets and maps take O(log n). Is there any STL which satisifies all requirements(insertion taking log n time is not a problem) or any function by which I can get number of elements in range [l,r] in log n time ?
I am not sure about maps but in set we can have complexity as O(logN) i.e. it = st.lower_bound(val) will give you the value greater than or equal to val in set in logN time. I got one of my solution passed using this which was not running by using standard way of lower_bound (tle).
For reference http://www.cplusplus.com/reference/set/set/lower_bound/
It can be done using Order statistics tree, learnt something new.
Reference : C++ STL: Policy based data structures - Codeforces
3 Likes
You have not understood the question properly. I am asking something else.
Thanx man !! Never knew such thing existed.
Sorry i didn’t noticed that you were asking for the number of elements b/w them. If it was vector we would have subtracted diff of upper and lower bound but it is not possible for sets.
Thank u for the link.