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

I have to implement BST myself?
Автор meijun, 10 лет назад, По-английски

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?

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?).

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

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

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

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

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

Well, a segment tree would be enough :).

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

    Could you please give some more details?

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

      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.

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

        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...

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

          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.

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

          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.

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

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 .

→ Ответить