habib_rahman's blog

By habib_rahman, history, 5 years ago, In English

I want to do binary search on a multiset, because I need to know "How many elements in the multiset greater or equal to x". And obviously I want to get the data in O(logn).

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Multisets support only lower bound and upper bound operations, and not operations of the type number of elements  ≥ X. For this purpose, you can use a BIT, or if the values are too large, then compression with a BIT.

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