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

×

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

rj25's gravatar image

4★rj25
2305
accept rate: 0%


It can be done using Order statistics tree, learnt something new. Reference : http://codeforces.com/blog/entry/11080

link

answered 07 Mar '18, 19:11

rj25's gravatar image

4★rj25
2305
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 http://www.cplusplus.com/reference/set/set/lower_bound/

link

answered 07 Mar '18, 16:06

vishesh_345's gravatar image

1★vishesh_345
2567
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★

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

link

answered 07 Mar '18, 19:21

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,409
×1,056
×279

question asked: 07 Mar '18, 14:42

question was seen: 385 times

last updated: 07 Mar '18, 19:39