• Firstly , my English is very poor ....
• Because this problem is about interval modify , we had better use the lazy function.
• let's create this struct
• struct segtree {
• int left , right; //the segtree's index's left and right
• long long sum , flag; // the segtree's interval's sum and flag
• }
• the flag is about lazy
• I just give you an example
• if you update interval is [1,100] , and variable is x;
• if you update all node , the time costs too much ,because you will update[1,1] , [2,2] ,...[100,100]
• But we needn't do this work.
• When we use this interval , we let the node's parent pass the flag to it.
• ..Sorry , poor English , You can see my code for understanging better.
• [Your text to link here...]
• (http://codeforces.net/contest/283/submission/12350779)`
• Actually , this problem has a better function, it solves more easier.
• my god I really don't know how to post it look clear= =

First my English is poor too...

Lazy Propagation: you don't need to update all of the elements in the segment,just update the parent when it's total overlap and mark it's children for later...

First: If you don't understand segment tree 100% watch this

segment tree:build,answer a query and normal update java code just under stand algorithm don't worry for it's programming language.

Lazy Propagation Article here

Easy and some hard problems Here