段樹範圍最小查詢

Question

我想了解分段樹。這是一個great tutorial，顯示如何找到範圍內的最小值。然而，有人說，「除了最後一層，所構建的分段樹的所有級別都將被完全填充，並且樹將成爲完全二叉樹，因爲我們總是在每個級別將分段分成兩半。」我不明白如何進行添加？例如，如果我們再添加兩個元素6和10 - 他們應該去哪裏？進入正確的子樹？如果是的話，會有5個不太平衡，兩個不平等。我是否應該重新排序樹並再次進行計算？

Answer 1

段樹的這種實現不支持添加操作，所以不可能添加新元素。