Я пытаюсь понять деревья сегментов. Это отличное руководство, в котором показано, как найти минимум в ассортименте. Однако там сказано, что «Все уровни построенного дерева сегментов будут полностью заполнены, кроме последнего уровня. Кроме того, дерево будет полным двоичным деревом, потому что мы всегда делим сегменты на две половины на каждом уровне». Я не понимаю, как происходит добавление? Например, если мы добавим еще два элемента 6 и 10 — куда они должны деваться? В правильное поддерево? Если да, то будет 5 не очень сбалансированных и половинок не равных. Должен ли я каким-то образом изменить порядок дерева и снова выполнить вычисления?
минимальный запрос диапазона дерева сегментов
Ответы (1)
Эта реализация дерева сегментов не поддерживает операцию добавления, поэтому невозможно добавить новый элемент.
person
kraskevich
schedule
01.10.2014
Можете ли вы привести пример, какая реализация поддерживает операцию добавления?
- person Bob; 01.10.2014
Вы можете использовать сбалансированное двоичное дерево поиска для хранения узлов дерева сегментов, чтобы сделать возможным добавление новых элементов.
- person kraskevich; 01.10.2014
Но при балансировке придется пересчитывать расстояния, что не очень эффективно.
- person Bob; 01.10.2014
Пересчет требуется только для тех узлов, которые повернуты или находятся на пути от корня к новому листу. Таких узлов всего
O(log N).
- person kraskevich; 01.10.2014
