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?
Auto comment: topic has been updated by xblwyc (previous revision, new revision, compare).
Basically all Balanced-BSTs such as Treaps, red-black trees, avl trees etc...
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..
http://mirror.codeforces.com/blog/entry/11080
That is exactly what I want! Thank u!
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.
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://mirror.codeforces.com/blog/entry/3767
Maybe you can just see the number as binary string and use a trie. It will be O(log RANGE) though.
That's just a dynamically allocated segment tree...
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.
Treap Tutorial in english:
part 1
Part 2
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.
Rope
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.
Can't we do this with a simple dynamic segment tree(as you say the range is big) and order statistics?