Jim_Moriarty_'s blog

Search of specific data structure
By Jim_Moriarty_, history, 5 years 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

»
5 years 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

→ Reply
»
5 years 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.

→ Reply