vijasi's blog

Number of elements having value <=x in a Set [Solved]
By vijasi, history, 5 years ago, In English

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.

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

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Try this

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can use Ordered Set

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply