I'm required to describe an implementation of a data structure that holds key,value pairs, which can be signed integers.
We need to be able to init() in O(1), insert(x) in O(logn), delete(x) in O(logn) and sumPrevious(x), which returns sum of values of the keys that are smaller than key 'x', in O(logn). An AVL rank tree, which rank is sum of values in sub-tree, should do the trick. So far so good.
Now I need to also implement maxSumPrevious(), which returns the key 'k' for which 'sumPrevious(k)' is maximal, in O(1). This is where I got stuck. Since inserting or deleting an element changes the 'sumPrevious' of ALL the elements bigger than it. I tried going in the direction of a different rank that updates in insertion/deletion, but it lead to nowhere.
Thank you in advance
maxSumPrevious(n)be the max prefix sum in the subtree $n$. For a node $n$ with children $\ell$ and $r$, $maxSumPrevious(n) = \max(maxSumPrevious(\ell), sum(\ell) + maxSumPrevious(r))$. $\endgroup$