= Структура =
Пусть есть множество <tex>m[0 \dots M-1]</tex> мы хотим записать эти данный в дерево.[[Файл:Boas.jpg.jpg|right|380px378px|thumb|корень дерева]]Будем называть наше дерево <tex>T</tex>.В корне(root) будут храниться: *массив детей размером <tex>sqrt M</tex> (T.children[]) *значение текущего минимума и максимума в дерево (T.min, T.max)*вспомогательный массив (T.aux)
Для удобства работы с деревом будем использовать <tex>k</tex> равные степени двойки.
Как уже было сказано выше, <tex>k</tex>-дерево хранит числа в интервале <tex>[0;2^k]</tex>. Тогда 1-дерево хранит информацию, содержатся ли в нем 0 и 1.
Элемент массива из детей с индексом Построим <tex>k</tex>-дерево, при <tex>i=k \lfloor xneq 1</Mtex>. В нем будут хранится:*массив <tex>children</tex>, состоящий из <tex>2^{1k/2}\rfloor</tex> является также деревом для множества <tex>k/2</tex>-деревьев*вспомогательное <tex>k/2</tex>[i sqrt(M) \dots (i+1) sqrt(M)- 1]дерево, которое назовем <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>i\ log_{2} (k)</tex> хранится , так как каждый следующий уровень дерева содержит числа, количество битов в которых в 2 раза меньше, чем в предыдущем. Во вспомогательном дереве только если занят элемент с индексом <tex>iaux</tex> в массиве детейбудем хранить все такие числа <tex>p</tex>, что дерево <tex>children[p]</tex> не пусто.
= Операции =
