Find an algorithm in RBTREE in O(logn)

Question

I need to find a data structure which I can do with the following actions:

• Build(S,k) - O(nlogn)
• Search(S,k) - O(logn)
• Insert(S,k) - O(logn)
• Delete(S,k) - O(logn)
• Decrease-Upto(s,k,d) - O(logn) - this method should subtract d(d>0) every node which is <=k

The obvious first choise was RedBlackTree.

However, I can't come to a solution regarding Decrease-Upto in O(Logn). what happens if k is greater then the max key in the tree - that case i gotta update the whole tree.

Can someone suggest otherwise ? maybe some tips ?

Answer 1

You can store an extra value in each node of the tree, let's call it delta. You add delta of a node to keys stored in all its descendant to get the actual keys. So, to get the actual value of a key in a particular node, you sum all deltas from the root to that node and add this sum to the stored key.

To do Decrease-Upto, you just change deltas of O(log n) nodes on one path from root.

You don't have to change the structure of the tree after this operation, because is doesn't change ordering of the keys.