403
правки
Изменения
→Структура
*массив <tex>children</tex>, состоящий из <tex>2^{k/2}</tex> <tex>k/2</tex>-деревьев
*вспомогательное <tex>k/2</tex>-дерево, которое назовем <tex>aux</tex>
*максимальный и минимальный элемент, хранящийся в этом дереве (если оно не является пустым), причем дополнительно в самом дереве эти элементы хранить не будем.
Пусть у нас есть <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> не пусто.
