Алгоритм для частного случая рангового дерева

Question

Я пытаюсь создать дерево рангов на основе дерева AVL со специальными требованиями. Допустим, у меня есть дерево AVL с узлами, у каждого узла есть 2 поля:

id, priority

мое дерево AVL отсортированопо идентификатору, также у меня есть функция:

foo(currentId, delta)

, которая понижает приоритет всех идентификаторов, который меньше или равен currentId на delta эта функция должна работать со сложностью O (log n), поэтому мой вопрос в том, какую дополнительную информацию мне нужно сохранить, чтобы иметь возможность вытолкнуть узел с highest priority на любом этапе with complexity O(1) (после использования также foo!).

P.S. Iпытался сохранить информацию о максимальном приоритете в правом поддереве, максимальном приоритете в левом поддереве, но после foo требуется много изменений.Это займет больше, чем просто O (log n).Заранее благодарим за любые хорошие идеи или хорошие книги о деревьях.

Answer 1

Вместо сохранения максимального приоритета, который появляется в каждом поддереве, для каждого узла c с родительским p сохраните в c разницу между максимальным приоритетом в поддереве c и максимальнымприоритет в поддереве р.Таким образом, вы можете обновить диапазон приоритетов за время O (log n) и все же найти элемент максимального приоритета за время O (log n).