Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $
AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than log(n). 


Not quite. In order to change all those entries, yes; but by searching for $x$ you can identify all nodes that have greater values: all nodes you visit and have key $&gt; x$, namely those where you go left, and their right subtrees.


  Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.


No, and that may be the key insight. If we increase all keys $&gt;x$ by some constant we maintain the search-tree property! In particular, you never increase a left son and not its parent!

These two observations lead us to the idea: use AVL-trees (or any balanced search tree, I daresay) and execute key increments lazily. For that, add to every node an integer inc that is initially $0$.

Now, a call updateKeys(x,v) proceeds as follows.


Search for x using usual BST search.
Whenever you go left at some node y, 


increase y.key by v and
increase y.right.inc by v.



This adds at most constant overhead per visited node, so it has the same $\Theta$-running-time as search.

We execute the updates whenever we traverse the tree anyway. That is, augment all four operations so that when they access some y.key they execute this first (if y.inc &gt; 0):

y.left.inc  += y.inc
y.right.inc += y.inc
y.key       += y.inc
y.inc        = 0


This adds at most a constant amount of effort per visited node for all the operations, so it does not change their $\Theta$-bounds on time. We do need a linear amount of extra memory, but that seems to be allowed.

Detailed pseudocode and proofs of correctness are good exercises.