You are not logged in. Please login at to post your questions!


STL + Binary Search


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

rj25's gravatar image

accept rate: 0%

Amm check this out i dont fully understand it though hope it might be of some help!


answered 07 Mar '18, 19:21

phantomhive's gravatar image

accept rate: 0%

It can be done using Order statistics tree, learnt something new. Reference :


answered 07 Mar '18, 19:11

rj25's gravatar image

accept rate: 0%

Thanx man !! Never knew such thing existed.

(07 Mar '18, 19:16) vivek_19982996★

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


answered 07 Mar '18, 16:06

vishesh_345's gravatar image

accept rate: 8%

edited 07 Mar '18, 16:10

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) vishesh_3451★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 07 Mar '18, 14:42

question was seen: 386 times

last updated: 07 Mar '18, 19:39