Двоичное дерево поиска со специальными операциями

Question

Предположим, у нас есть нормальное двоичное дерево поиска по целым числам.

Меня интересует количество элементов, кратное 3 и превышающее данное число x. Также меня интересует количество элементов, кратное 3 и строго между двумя заданными числами x1, x2 с x1

Answer 1

В каждом узле вы можете вести подсчет количества, кратного 3, в поддереве этого узла.

Эти подсчеты можно поддерживать без изменения сложности операций добавления / удаления / вращения / перебалансировки.

Затем, чтобы посчитать количество, кратное 3, больше, чем x, вы ищете x.Всякий раз, когда вы идете налево на узле (потому что это> x), вы добавляете счетчик из этого узла и вычитаете счетчик из узла, в который вы перемещаетесь.

Если вы найдете x во внутреннем узле, добавьтесчитать от своего правого ребенка.