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] ?
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