Найдите алгоритм в rbtree в O (logn)

Question

Мне нужно найти структуру данных, которую я могу сделать со следующими действиями:

• Build (s, k) - O (nlogn)
• Поиск (s, k) - O (logn)
• Вставьте (s, k) - O (logn)
• Удалить (s, k) - O (logn)
• Уменьшение -апто (s, k, d) - O (logn) - Этот метод должен вычесть d (d> 0) каждый узел, который <= k

Очевидным первым выбором был Redblacktree.

Тем не менее, я не могу прийти к решению, касающемуся уменьшения в Opto в O (logn). Что произойдет, если K будет больше, то максимальный ключ в дереве - в этом случае я должен обновить все дерево.

Кто -нибудь может предложить иначе? Может быть, несколько советов?

Answer 1

Вы можете сохранить дополнительное значение в каждом узле дерева, давайте назовем это Delta. Вы добавляете дельту узла в ключи, хранящиеся во всех его потоках, чтобы получить фактические ключи. Таким образом, чтобы получить фактическое значение ключа в конкретном узле, вы суммируете все Deltas от корня в этот узел и добавляете эту сумму в сохраненный ключ.

Сделать Decrease-Upto, вы просто измените Deltas of O (log n) узлы на одном пути от корня.

Вам не нужно менять структуру дерева после этой операции, потому что не меняет упорядочение ключей.