228
правок
Изменения
→Структура
Будем называть наше дерево <tex>T</tex>.
В корне(root) будут храниться:
*массив детей размером <tex>sqrt{M}</tex> (T.children[])
*значение текущего минимума и максимума в дерево (T.min, T.max)
*вспомогательный массив (T.aux)
Элемент массива из детей с индексом <tex>i=\lfloor x/M^{1/2}\rfloor</tex> является также деревом для множества <tex>[i<tex>sqrt{M^1/2}</tex> .. (i+1)<tex>sqrt{M^1/2}</tex> - 1]</tex>
В вспомогательном дереве хранится информация о том, какие клетки уже заняты. То есть значение <tex>i</tex> хранится в вспомогательном дереве только если занят элемент с индексом <tex>i</tex> в массиве детей.
