Segment tree

Please help ,I am new to segment tree topic… I stuck on this code…

int query_tree(int node, int a, int b, int i, int j) {

if(a > b || a > j || b < i) return -inf; // Out of range

if(a >= i && b <= j) // Current segment is totally within range [i, j]
	return tree[node];

int q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child
int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child

int res = max(q1, q2); // Return final result

return res;

}

In the above code ,how this line is working:

if(a >= i && b <= j) // Current segment is totally within range [i, j]
return tree[node];

If [a,b] is within [i,j] ,then how can it ensure that maximum value will occur within [a,b] ? what about interval [i,a] ans [b,j] ?

Hi,

Let me see if I can help you out now!

There is a difference between the original array which we are querying upon and the segment tree that we have built over that array.

Suppose that a given range [2,4], for the sake of an example, is given as query, such that in your example the start of the query = 2 and end of query = 4.

If your node in the segtree is covering the range, for example, [1,7], then you can be 100% sure that the maximum value in the range [2,4] will also be the maximum value in the range [1,7] because the limits of the query 2 and 4 are contained within the range covered by the node which means that you don’t need to recurse down the tree anymore and simply return the value of that node.

If this is not the case, then you begin visiting the descendents of that node recursively and returning the desired operation (maximum in this case) at the end.

         Node covers range
               [1..7]
               /    \
              /      \
        left child   right child

But oh wait, we want to know the maximum in the range [2,4].

Well [2,4] is inside the range covered by the node.

          Node covers range
            [1..[2,4]..7] --> Since range [2,4] is inside and we already have answer for range [1,7] we return the value of that node
               /    \
              /      \
        left child   right child
1 Like

@kuruma >> if our query is [2,4], the the nodes visited must be

[1,7]-->[1,4]-->[1,2]-->[2,2]
             |
              ->[3,4]

explanation:

  • cur seg = [1,7], query seg = [2,4] => current segment is NOT totally contained in the query seg, so we query both its children.
  • cur seg = [1,4], query seg = [2,4] => current segment is NOT totally contained in the query seg, so we query both its children.
    • cur seg = [1,2], query seg = [2,4] => NOT totally contained, call children.
      • cur seg = [1,1], query seg = [2,4] => out of range returing -inf.
      • cur seg = [2,2], query seg = [2,4] => cur seg is CONTAINED in qry seg, returning max stored in cur node.
    • cur seg = [3,4], query seg = [2,4] => cur seg is CONTAINED in qry seg, returning max stored in cur node.
  • cur seg = [5,7], query seg = [2,4] => out of range returning -inf.

correct me if i’am wrong.

2 Likes

@kuruma >> i think you got it wrong, [cant fit my comment in here, commented as answer below].

1 Like