You must use lazy propagation

useful link

Well, the idea is the same. Let each node have a value "add", which says by which number should we increase all the elements belonging to the range of that node. Let us have a query (a,b,val) which means we should increase all values from a to b inclusive by val. Let's do it recursively with function Add(a,b,val). If we come to a node which has has range (l,r) then
1) if (a > r) or (b < l) we stop processing that node since the query has nothing to do with the range of that node.
2) if (a <= l) and (b >= r) we increase the value "add" of that node by "val" since the query covers the range of the node.
3) else we call the same procedure with the same arguments (a,b,val) in the left and the right son.
In order to count the sum we should add some code lines in the end of the Add() function. Sum of the current node be the sum of the both sons plus their ("adds") * (size of their range). This may seem vague, but if get down to my code below and look at it once or twice you will get the idea quickly.

The Sum(a,b) function:
1) if (a > r) or (b < l) we stop processing that node since the query has nothing to do with the range of that node and return 0.
2) if (a <= l) and (b >= r) we return the sum which was stored already in that node plus its ("add") * (r-l+1).
3) else return L.Sum(a,b,val) + R.Sum(a,b,val) + (current "add")*(size of intersection between [a,b] and [l,r]) which equals (min(b,r)-max(a,l)+1).

Code on C#.
http://pastebin.com/X3UrHk1N

By the way many people implement this using standard arrays so I do not imply in any way that my Segment Tree in classes is the only correct implementation. Surf the internet to find the standard array implementation if you don't like classes :)

You can find a good tutorial on Segment Trees here. Good luck!