×

# STL + Binary Search

 0 1 In vector(sorted) when we want to find number of elements in range [l,r] we simple use upper_bound(r)- 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 ? asked 07 Mar '18, 14:42 4★rj25 230●5 accept rate: 0%

 0 Amm check this out i dont fully understand it though hope it might be of some help! answered 07 Mar '18, 19:21 94●4 accept rate: 0%
 3 It can be done using Order statistics tree, learnt something new. Reference : http://codeforces.com/blog/entry/11080 answered 07 Mar '18, 19:11 4★rj25 230●5 accept rate: 0% Thanx man !! Never knew such thing existed. (07 Mar '18, 19:16)
 0 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). answered 07 Mar '18, 16:06 256●7 accept rate: 8% You have not understood the question properly. I am asking something else. (07 Mar '18, 19:10) rj254★ 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. (07 Mar '18, 19:38)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,409
×1,056
×279

question asked: 07 Mar '18, 14:42

question was seen: 386 times

last updated: 07 Mar '18, 19:39