meijun's blog

I have to implement BST myself?
By meijun, 10 years ago, In English

I have a array of numbers. The size of the array is about 1e5. This count of operations is about 1e5.

There are 3 types of operation:

  1. change the i-th (position) number;

  2. query the k-th (big or small) number's value;

  3. query the i-th (position) number's rank (big or small).

I have to implement BST myself?

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

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

If you want to solve that problem using BST, yes, you have to implement it, java and c++ have implemented BSTs but its not easy to augment the nodes (or impossible?).

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

    Because RB tree is implemented in STL, maybe it's possible to use BST not implemented by myself.

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

    In std::map values can be modified. For modifying keys, one will have to .erase() old one and insert new one.

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

Well, a segment tree would be enough :).

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

    Could you please give some more details?

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

      Compress all integers to the range 1...2e5.

      Then make a segment tree on values (1, 2e5) in which node (i, j) holds the count of integers in the range [i,j] in the entire array

      Queries should be pretty similar to the binary search tree version from here.

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

        For query 3, I can solve it in O(log(n)).

        But for query 2, I can solve it using binary search. Time O(log2(n)).

        If I want query the value(query 2's answer)'s original position, I don't know how to solve it. Please help...

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

          Querying "original position" of k-th number doesn't make sense here as there could be multiple elements with the same value.

          But ofcourse, you can access the set of positions occupied by the k-th number by associating a std::set with each number.

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

          This requires some knowledge of how the segtree is organized.

          Think about how you would do it in a bst: you'd look at the count of elements in the left subtree, and decide based on that whether to go to left or right subtree.

          Here do the same thing: recurse from the top to bottom, if the count in the left subtree is not enough, go the right, else go to the left, until you reach the element you want.

          You can do the same thing with a bit, which would be even faster. I believe the topcoder tutorial has code for that.

          → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

You can also use order statistics tree implemented in SGI STL.

Also somebody above recommended to compress numbers with segment tree. But you can solve problem with segment tree without compressing like described here. Also in that entry described how to solve the second query in .

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

    Thanks!!!

    This is what I want really!

    Thanks again~ :D

    → Reply