xblwyc's blog

Any data structure supporting log(n) update, delete and index query?
By xblwyc, history, 9 years ago, In English

Suppose we are going to insert n numbers(may have duplicates), how would you design a data structure that supports the following functions in O(log n) time. The value range is very large.

int insert(int val) // return the index(how many numbers that are smaller than val) of the val

int find(int k) // return the kth minimal value.

void delete(int val) // delete the value

For offline algorithm(We can know all the values before), using binary index tree will be enough. But without that, how can we implement it?

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

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

Auto comment: topic has been updated by xblwyc (previous revision, new revision, compare).

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

Basically all Balanced-BSTs such as Treaps, red-black trees, avl trees etc...

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

    You mean using an additional variables to count the number of nodes of the subtree? That's a good idea.. But do we have any functions/easy ways to implement this idea? I feel it painful to code the whole BST and keep it balanced..

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

      http://codeforces.net/blog/entry/11080

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

        That is exactly what I want! Thank u!

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

      Here is the blog, about the built-in set that performs described operations. As for duplicates, you may maintain their count, and use pair <int, int> to keep them.

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

      C++ standard data structures are certainly handy in general and appropriate for the mentioned problem, but I'd just like to clarify, that coding Treap with such functionality isn't painful at all. And if you learn to write it easily, you will gain the ability to solve more complicated tasks, which the C++ standard data structures aren't capable of.

      In case you're just not familiar with Treap, this post may be helpful: http://codeforces.net/blog/entry/3767

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

Maybe you can just see the number as binary string and use a trie. It will be O(log RANGE) though.

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

    That's just a dynamically allocated segment tree...

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

Read this article about Treap.

Treap supports all these queries and more, and easy to code.

note that, this article only in russian, but you can use google translation or any other and will understand well.

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

Thanks to the everyone above! I searched "treap" and find "Rank tree", which is the data structure exactly aimed at solving my problem and is implemented by treap.

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

Rope

→ Reply
»
9 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

You can use AVL tree for this.

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. Insertion, deletion and searching operations are O(log n) in AVL tree.

insertion in AVL http://ideone.com/jd3ljs

deletion in AVL http://ideone.com/lbWsmS

search in AVL http://ideone.com/4CLYzI

This post may be helpful for u to get informations about avl tree: https://courses.cs.washington.edu/courses/cse373/06sp/handouts/lecture12.pdf

I hope, this will be helpful.

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

Can't we do this with a simple dynamic segment tree(as you say the range is big) and order statistics?

→ Reply