10

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?

adijo
  • 1,450
  • 1
  • 14
  • 20

5 Answers5

12

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.

kraskevich
  • 18,368
  • 4
  • 33
  • 45
  • Can you please provide an example? It will make things clearer for future readers too! – adijo Nov 30 '14 at 04:49
  • Kraskevich's answer is correct except the last sentence. According to him, for `T(l, r)` and `n = l - r`, `2 * log n` nodes can be used at most. If it is true, for `T(1, 17)`, 8 nodes can be used but the true answer is actually 6. The answer should be `2 * log n - 2`, because he assumed that we can use both of nodes of level 1. However, in this case, we need to get the root instead of level 1 nodes. Also, we cannot get any of these two nodes, because it means there is no node is used in the higher levels. For `T(1, 17)`, `[1, 9)` and `[9-17]` nodes at level 1. If we use `[1, 9)`, we discard ch – Dorukhan Arslan Feb 22 '16 at 21:33
5

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.

enter image description here

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)

Tokala Sai Teja
  • 650
  • 8
  • 9
1

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 enter image description here

Oleksandr Papchenko
  • 2,071
  • 21
  • 30
  • I think what other answers want to suggest is that **at each level atmost 2 nodes will be expanded(i.e a recursive call will be made)**, so in the example, you have given even though at some levels *4 nodes may be visited(marked as 'X')* however only on 2 of them a recursive call will be done and they will be expanded further(out of the 4 nodes) for the other 2 the value will simply be returned.because only complexity is needed so we don't consider the fact that at some level 4-nodes will be visited, and directly consider the maximum number of recursive calls made at each level(which is 2). – Freelancer Jul 28 '20 at 19:49
  • A nice explanation is provided here [codeforces EDU](https://codeforces.com/edu/course/2/lesson/4), directly seek to 9:30 if someone is interested only with this part(you may have to join the course, the video is the first part of the segment tree series). – Freelancer Jul 28 '20 at 19:54
0

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.

Novice
  • 155
  • 3
  • 14
0

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 )

kanishk verma
  • 382
  • 2
  • 9