403
правки
Изменения
→Структура
Пусть у нас есть <tex>k</tex>-битное число <tex>x</tex>. Разобьем это число таким образом, что <tex>high(x)</tex> {{---}} число, соответствующее <tex>k/2</tex> старшим битам числа <tex>x</tex>, а <tex>low(x)</tex> соответствует <tex>k/2</tex> младшим битам. Тогда информации, хранится ли в данном дереве число <tex>x</tex>, эквивалентна информации, содержится ли в дереве <tex>children[high(x)]</tex> число <tex>low(x)</tex>.
Нетрудно увидеть, что высота подобного дерева <tex>\ log_{2} (k)</tex>, так как каждый следующий уровень дерева содержит числа, количество битов в которых в 2 раза меньше, чем в предыдущем.
Во вспомогательном дереве <tex>aux</tex> будем хранить все такие числа <tex>p</tex>, что дерево <tex>children[p]</tex> не пусто.
