I use very simple algo, prompt other algo please.

Edited by author 10.08.2011 15:32

Segment tree with range update,  obviously.
And even Fenwick tree with range increment. (Petr described such a Fenwick tree in his blog)