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

Please help
Автор I_LOVE_METSUKA, история, 7 лет назад, По-английски

I want to add numbers to a set of integers and answer a query how many numbers are there which are less than a given number K. What is an efficient way to implement this other than BIT?

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

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I don't know what is BIT, but you can simply use a vector as a set (find exact position for a newer element using lower_bound and inserting if element at this position isn't equal to the one you're trying to add). Then, just using distance(vect.begin(), lower_bound(vect.begin(), vect.end(), K)) — you can obtain the answer for a query.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    inserting in the middle of a vector is O(n).

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Well, yes. Then, you could insert in a set first, then do copy(iset.begin(), iset.end(), back_inserter(vect)) and perform queries on the vector as stated above. I expect copying to have linear complexity.

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

C++ STL: Policy based data structures

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

Using a treap to implement a set(set in STL),it is O(log n).

→ Ответить