Jim_Moriarty_'s blog

By Jim_Moriarty_, history, 2 months ago, In English,

Is there a data structure which performs O(1) or O(logn) insertion at back and same for removal and we can find the number of elements less than K (any particular element ) in O(logn) if the data structure is already sorted (means binary search is applicable )

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

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Order Statistics Tree. You can get the order of the element and it's the number of elements less than it. Order, deletion and insertion take O(log n) time. Here's its Wiki article

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You could certainly do that with a treap, just store keys along with subtree sizes.