Answers to: STL + Binary Searchhttps://discuss.codechef.com/questions/124050/stl-binary-search<p>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 ?</p>enWed, 07 Mar 2018 19:21:55 +0530Answer by phantomhivehttps://discuss.codechef.com/questions/124050/stl-binary-search/124060<p>Amm check <a href="http://codeforces.com/blog/entry/11080">this</a> out i dont fully understand it though hope it might be of some help!</p>phantomhiveWed, 07 Mar 2018 19:21:55 +0530https://discuss.codechef.com/questions/124050/stl-binary-search/124060Answer by rj25https://discuss.codechef.com/questions/124050/stl-binary-search/124055<p>It can be done using Order statistics tree, learnt something new.
Reference : <a href="http://codeforces.com/blog/entry/11080">http://codeforces.com/blog/entry/11080</a></p>rj25Wed, 07 Mar 2018 19:11:31 +0530https://discuss.codechef.com/questions/124050/stl-binary-search/124055Answer by vishesh_345https://discuss.codechef.com/questions/124050/stl-binary-search/124052<p>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).</p>
<p>For reference <a href="http://www.cplusplus.com/reference/set/set/lower_bound/">http://www.cplusplus.com/reference/set/set/lower_bound/</a></p>vishesh_345Wed, 07 Mar 2018 16:06:59 +0530https://discuss.codechef.com/questions/124050/stl-binary-search/124052