Algorithm for a special case of a rank tree

Question

I'm trying to create some rank tree based on the AVL tree with special requirements, let's say that I have an AVL tree with nodes, each node has 2 fields:

id, priority

my AVL tree is sorted by id, also I have a function:

foo(currentId, delta)

which reduces the priority of all identifiers that are less than or equal currentIdto delta this function should work with O (log n) complexity, so my question is what additional information do I need to save in order to be able to <node with highest priorityat any stage with complexity O(1)(after using foo also!).

P.S.I tried to save information about the maximum priority in the right subtree, the maximum priority in the left subtree, but it needs a lot of changes after foo. It takes more than just O (log n). Thanks in advance for good ideas or good books about trees.

Answer 1

Instead of storing the priority of the maximum that appears in each subtree, for each node c with the parent p, store the difference in cbetween the highest priority in the c subtree and the highest priority in the p-subtree. That way you can update a series of priorities in O (log n) time and still find the highest priority element in O (log n).