Hi! You might look up for "lazy propagation". There are some interesting explications and also code examples.

Make a segment tree as you normally do and at each node store the sum of all elements that are in it's range.

When you do range updates, just like when you do range queries, you stop when you reach a node whose range is contained by the range of the update. You can now calculate the new value of this node. Say this node, has in it's range elements from i to j. All elements get multiplied by k. So, the new sum for this range will be: (A[i] + A[i+1].. A[j]) * k = old_sum * k

After you update this node, normally, you will also have to update all of the subtree similarly. However, instead of doing that, you could just store a variable lazy at each node, that tells you that all of the nodes below this node need to be multiplied by value of lazy. By default this variable should be set to 1. Whenever updates stop at a node, you should just multiply k to lazy.

Now, whenever you are doing a query/update, and reach a node whose lazy value is not 1. If you are not stopping at this node, but going further, then the lazy value should be propagated downwards, that is, you multiply lazy[node] to lazy[left_child] and lazy[right_child]. Also, multiply lazy[node] to sum[left_child] and sum[right_child]. Finally, set lazy[node] = 1. So you are shifting the value of lazy from a node onto the child. This step is only done whenever you are at a node whose lazy value is not 1, but you need to visit it's children.

This reduce updates to logN. And queries are also logN because you are shifting lazy values only when you already need to visit those nodes by queries.

Hope this helps.

Thanks so much guys! Perfectly clear :) !

I wrote a solution but gives me WA. Can someone tell me where I'm wrong?

Code