Algorithm for the special case of rank tree

Question

I'm trying to create some rank tree based on AVL tree with special requirements, lets assume that I have 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 lowers the priority of the all ids which is less or equal to currentId by delta this function has to work with complexity O(log n), so my question is which additional information do I need to store to be able to pop the node with the highest priority at any stage with complexity O(1) (after using foo also!).

P.S. I tried to store info about max priority in the right subtree, max priority in the left subtree, but it needs a lot of changes after foo. It will take more than just O(log n). Thanks in advance for any good ideas or good books about Trees.

Answer 1

Rather than store the maximum priority that appears in each subtree, for each node c with parent p, store in c the difference between the maximum priority in c's subtree and the maximum priority in p's subtree. This way, you can update a range of priorities in O(log n) time, and still find the element of maximum priority in O(log n) time.