### GodKing's blog

By GodKing, history, 4 weeks ago, ,

Is there a way to find index of a element which is in set. between time complexity o(1)... o(log(n))

• +11

 » 4 weeks ago, # |   0
•  » » 3 weeks ago, # ^ |   0 thanks!
 » 4 weeks ago, # |   0 use ordered_set
 » 3 weeks ago, # |   +9 use the rb_tree_tag included in ext/pb_ds/tree_policy.hpp; although you can use Binary Indexed Tree + Binary Search to do it in $O(\log^2n)$ time (I think it's faster), you even can do Binary Lifting (as a kind of binary search) to perform it in $O(\log n)$. The bad thing is when you must do it fully dynamic and the elements are ~$10^9$
 » 3 weeks ago, # |   -14 i think we may use lower_bound or upper_bound for o(log(n))
•  » » 3 weeks ago, # ^ |   0 elaborate.
•  » » » 3 weeks ago, # ^ |   -13 you can refer this
•  » » 3 weeks ago, # ^ |   +1 What the heck? You won't be able to get the index of the set using that. As mentioned above, the easiest way is to use PBDS. I assume your method only works if the set is fixed which off-course, not applicable for most of the problems.
 » 3 weeks ago, # | ← Rev. 3 →   0 That is incorrect +_+
•  » » 3 weeks ago, # ^ |   0 STL won't work, The set in C++ STL uses bidirectional iterators, it's like a BST inside, you can't find the index of element in a set without using PBDS.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 Aahan I realized that I misunderstood it, Can you provide how to use PBDS here?
•  » » » » 3 weeks ago, # ^ |   +2