Segment tree

general
,
1

Was studying segment tree from http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

but was uanble to figure out as why- ““int getMid(int s, int e) { return s + (e -s)/2; }””.
Here the getMid funct should be returning ((s+e)/2) and not the above one.Plz help unable to figure out.

1 Like
2

s+(e-s)/2 = (s+e)/2 … Both expressions are valid as they yield the same result, try and simplify the first one.

1 Like
3

The reason for returning average value in such a way generally is to avoid integer overflow.
For reference http://stackoverflow.com/questions/3816446/how-can-i-safely-average-two-unsigned-ints-in-c

1 Like
4

kk could u explain what is being done getSumUtil fuct

if (qs <= ss && qe >= se)
    return st[index];
5

The comments already explain that… If the current segment is inside of our query range just return its value… The best way to solve segment trees is to try and solve some problems with it… The link you’re following is great but the code is way too big to start with… I suggest you to read the topcoder tutorial too: http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static#Segment_Trees

1 Like