Segment Tree Query

general
,
1

Typically the range query function of segment tree looks like

int query(i, j, low, high, pos){

   //some code

 if(i <= low and j <= high){
      return ST[pos]
 }

//some more code

}

I want to know, in worst case, how many times the line “return ST[pos]” would get executed. In other words, what is the maximum number of nodes required to represent a sub-array fully in a segment tree.

Please do not forget to justify your answer.

2

Lets try to look at this level wise. The maximum number of nodes returned in any level of the tree would be 2. This is true because, if there were three nodes to be returned from a level, two of them would have a common node containing both of them, at a higher level and that would be returned instead. One other property of segment trees is that at any level, you would expand at most two nodes. So, if you ever return 2 nodes from the same level, you wouldn’t go further down in the tree. So the worst case would be when you go down to the lowest level of the tree, returning 1 node at every level. One situation where this will happen is when the size of your tree is a power of 2 and you are querying the range containing all but the last position i.e. 1 to N-1 where N=2^k, in this case you’d return k nodes. So, the maximum number of nodes is O(Log N)

1 Like