What is the best way to perform queries on set such that each query would be either of type : 1. Add an element to a set. 2. Increase all elements of the set by some constant. 3. Print the K'th largest element from the set.
Any tutorials would be helpful.
Also if there is another query(including the above 3) remove an element from set, then what can be the best solution?
You can use a treap to support all 4 types of queries in $$$O(n lg n)$$$. This is the most basic and common use of a treap.
But I'd like to discuss a sqrt decomposition solution as well (not supporting remove queries). We will store all the values in a sorted array. Whenever an insert query comes, we will put it into a buffer. When the size of the buffer becomes more than $$$\sqrt n$$$ we will rebuild the whole array. The increase query can be done pretty easily, just keep a lazy value for the array, and update all the current buffer values manually. Now, the kth element. We can easily do it with binary search, but it will bring something like $$$O(\sqrt n \lg n)$$$ complexity. So we are going to do another sqrt decomp. on the array. We will split the array into $$$\sqrt n$$$ chunks as well. Then we can easily do two pointer walk through our buffer and the array, achieving $$$O(\sqrt n)$$$ per query.
EDIT: You can also support remove queries using the same idea as buffer. Whenever a remove query comes, two cases can happen. It removes an element from the buffer or from the array. If it removes from the buffer, it's very easy to do. On the other case, it creates a hole in the array. We just mark it as deleted, but keep it in the array. When the number of holes become more than $$$\sqrt n$$$ — rebuild. Modify all the other queries likewise.
Note: It can't solve the whole problem, but it seems interesting.
You can use treap, like arman_ferdous mentioned. You can also use some policy-based data structures like
ordered_set
to maintain some of the operations. Where you will be able to perform these operations:Although it can't handle updates, I think it may help. Actually it can but the complexity is high. here is a link for
ordered_set
.You can handle the updates by maintaining their sum separately. When inserting or deleting $$$x$$$, you instead insert/delete the adjusted value $$$x - sum$$$.
Wow, nice trick :o and thanks