How can we prove that the update and query operations on a segment tree (http://letuskode.blogspot.in/2013/01/segtrees.html) (not to be confused with an interval tree) are O(log n)?
I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and right sub-trees. If we could prove that one of these calls terminates fairly quickly, the time complexity would be logarithmically bounded. But how do we prove this?
Lemma: at most 2 nodes are used at each level of the tree(a level is set of nodes with a fixed distance from the root).
Proof: Let's assume that at the level h at least 3 nodes were used(let's call them L, M and R). It means that the entire interval from the left bound of the L node to the right bound of the R node lies inside the query range. That's why M is fully covered by a node(let's call it UP) from the h - 1 level that fully lies inside the query range. But it implies that M could not be visited at all because the traversal would stop in the UP node or higher. Here are some pictures to clarify this step of the proof:
h - 1: UP UP UP
/\ /\ /\
h: L M R L M R L M R
That's why at most two nodes at each level are used. There are only log N levels in a segment tree so at most 2 * log N are used in total.
The claim is that there are at most 2 nodes which are expanded at each level. We will prove this by contradiction. Consider the segment tree given below.
Let's say that there are 3 nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to the right most node, then the full range of the middle node is covered. Thus, this node will immediately return the value and won't be expanded. Thus, we prove that at each level, we expand at most 2 nodes and since there are logn levels, the nodes that are expanded are 2⋅logn=Θ(logn)
If we prove that there at most N nodes to visit on each level and knowing that Binary segment tree has max logN height - we can say that query operatioin has is O(LogN) complexity. Other answers tell you that there at most 2 nodes to visit on each level but i assume that there at most 4 nodes to visit 4 nodes are visited on the level. You can find the same statement without proof in other sources like Geek for Geeks
Other answers show you too small segment tree. Consider this example: Segment tree with leaf nodes size - 16, indexes start from zero. You are looking for the range [0-14]
See example: Crossed are nodes that we are visiting
At each level (L) of tree there would be at max 2 nodes which could have partial overlap. (If unable to prove - why ?, please mention)
So, at level (L+1) we have to explore at max 4 nodes. and total height/levels in the tree is O(log(N)) (where N is number of nodes). Hence time complexity is O(4*Log(N)) ~ O(Log(N)).
PS: Please refer diagram attached by @Oleksandr Papchenko to get better understanding.
