段树范围最小查询

Question

我想了解分段树。这是一个great tutorial，显示如何找到范围内的最小值。然而，有人说，“除了最后一层，所构建的分段树的所有级别都将被完全填充，并且树将成为完全二叉树，因为我们总是在每个级别将分段分成两半。”我不明白如何进行添加？例如，如果我们再添加两个元素6和10 - 他们应该去哪里？进入正确的子树？如果是的话，会有5个不太平衡，两个不平等。我是否应该重新排序树并再次进行计算？

Answer 1

段树的这种实现不支持添加操作，所以不可能添加新元素。