GodKing's blog

By GodKing, history, 4 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

use ordered_set

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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, # |
  Vote: I like it -14 Vote: I do not like it

i think we may use lower_bound or upper_bound for o(log(n))

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    elaborate.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

That is incorrect +_+

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.