Need help with Segment Tree implementation

I am unable to understand the implementation given here.
I understand what a segment tree is and how it works, but I am unable to write a function for making one from a given array. Please explain the constructSTUtil and constructST functions.

Hope this will hel you Topcoder

void initialize(intnode, int b, int e, int M[MAXIND], int A[MAXN], int N) { if (b == e) M[node] = b; else { //compute the values in the left and right subtrees initialize(2 * node, b, (b + e) / 2, M, A, N); initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A, N); //search for the minimum value in the first and //second half of the interval if (A[M[2 * node]] <= A[M[2 * node + 1]]) M[node] = M[2 * node]; else M[node] = M[2 * node + 1]; } }

I am unable to understand these statements from this function : if (A[M[2 * node]] <= A[M[2 * node + 1]]) M[node] = M[2 * node]; else M[node] = M[2 * node + 1]; }

What are they doing?

A node [L,R] of segment tree stores the index of mininum number from the array A[] in the interval [L,R].
Now we compute it recursively.node[L,R] will have two childrens with interval [L,R/2] and [R/2+1,R] after computing values for these two children we compute the value for node[L,R].If minimum of [L,R/2] i.e. A[M[2node]]<=A[M[2node + 1]](i.e. minimum of node [R/2+1,R]) then the minimum of node[L,R] will be minimum of [L,R/2] else minimum of [R/2+1,R].
M[] stores the index with minimum value from array A[].

1 Like