Segment tree time complexity analysis

Question

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?

Answer 1

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.

Answer 2

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 log⁡n levels, the nodes that are expanded are 2⋅logn=Θ(logn)

Answer 3

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.

Answer 4

I will try to give simple mathematical explanation.

Look at the code below . As per the segment tree implementation for range_query

int query(int node, int st, int end, int l, int r)
{
    /*if range lies inside the query range*/
    if(l <= st && end <= r )
    {
        return tree[node];
    }
    /*If range is totally outside the query range*/
    if(st>r || end<l)
    return INT_MAX;
    
  /*If query range intersects both the children*/
    int mid = (st+end)/2;
    int ans1 = query(2*node, st, mid, l, r);
    int ans2 = query(2*node+1, mid+1, end, l, r);   
    return min(ans1, ans2); 
}

you go left and right and if its range then you return value.

So at each level 2 nodes are selected let's call LeftMost and rightMost. If say some other node is selected in between called mid one, then their least common ancestor must have been same and that range would have been included. thus

thus , For segment tree with logN levels. Search at each level = 2

Total search = (search at each level ) * (number of levels) = (2logN)

Therefore search complexity = O(2logN) ~ O(logN).

P.S for space complexity (https://codeforces.com/blog/entry/49939 )

Answer 5

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