I am trying to understand segment trees. This is a great tutorial that shows how to find a minimum in range. However, it is said there that "All levels of the constructed segment tree will be completely filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments in two halves at every level.". I do not understand how adding is performed? For example, if we add two more elements 6 and 10 - where should they go? Into the right subtree? If yes, there will be 5 not very balanced and halves are not equal. Should I somehow reorder the tree and do computations again?
This implementation of a segment tree does not support add operation, so it is not possible to add a new element.