Блог пользователя Jim_Moriarty_

Search of specific data structure
Автор Jim_Moriarty_, история, 5 лет назад, По-английски

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 )

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить