Bur's blog

The number of elements less then x
By Bur, history, 6 years ago, In English

This problem I meet very often: there is a set, in which we can add element, also we can erase any element. The problem is to count the number of elements less then x.

Sure, the problem can be solved with treap or something like that, but can it be solved with std::set or other already released data structures?

Any ideas?

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

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

It can be solved with C++ SGI STL tree. link

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

STL policy based data structures: order_of_key() is what you're looking for.

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

you too can use sqrt descomposition — mipt item 4.

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

Actually, if the problem allows that you can doing this work offline, you can easily solve it by using Binary Indexed Tree and Hashing:)

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    yes! you too can use online segment tree on air! (update and query in [1, maxElement]). O(q logmaxElement). This can be implemented without pointers!

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      If Max Element is too big to store in an array:

      1- Online: You can use dynamic segment tree or any variation of it.

      2- Offline: You can use index compression with regular BIT.

      → Reply