I_LOVE_METSUKA's blog

Please help
By I_LOVE_METSUKA, history, 6 years ago, In English

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?

  • Vote: I like it
  • -38
  • Vote: I do not like it

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

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.

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

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

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

      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.

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

        Just sort the vector using sort(v.begin(),v.end())

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

C++ STL: Policy based data structures

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

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

→ Reply