Segment tree SPOJ WA

general
, , ,
1

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


[2]
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


  [1]: http://www.spoj.com/problems/HORRIBLE/
  [2]: https://pastebin.com/f2N3iSig
2

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

3 Likes
3

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:https://discuss.codechef.com/questions/102348/segment-tree-approach-for-problem-solving

1 Like