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

Автор vijasi, история, 5 лет назад, По-английски

Hello

Is there any easy way to implement a set supporting following 2 operations in O(log(n)) ?

1)Insertion
2)Count of elements in the set having value <= x. (x is an Integer)

Values inside set can be from 1 to 1e9.

I am sorry if this in an easy/standard problem.

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

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

You can use Ordered Set

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

Auto comment: topic has been updated by vijasi (previous revision, new revision, compare).

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

A set can't do the 2nd operation in O(log(n))
but an ordered set can check Policy-based data structures