Segment tree SPOJ WA

I am getting WA on SPOJ [HORRIBLE][1]
here is my

I saw other's user code, but I don't know why they are updating like this

> tree[pos] +=(val*((high-low+1)));

instead of

> tree[pos] +=val;
> in line number 30 & 42


You are adding ‘val’ to all numbers in some range. Each node in the segment tree is responsible for some range, [low,high]. Now, if each position in the range that a node is responsible for has ‘val’ added to it, then wouldn’t the overall sum increase by val*(number of elements in the range = high-low+1) ?


thanks @hemanth_1 for such legit answer.Can you please take out some time to answer this question of mine related to seg_tree.Here is the link:

1 Like