Segment tree time complexity analysis

data-structures, segment-tree, time-complexity

Solution

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.

Problem

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?

Original source