I have a few doubts regarding segment trees range updates.
- I know how to use a segment tree for range query and single element update. But how do I use it for range updates as well as range query? For example, if the question is to find sum of elements in a range and add ‘v’ to all elements in the range, how do I do it?
- In the problem FlipCoins , I saw some solutions. They use another variable flip along with the head count. What is the purpose of that? I mean, why don’t we simply visit all the nodes in given range and flip the number of heads (interval size - previous number of heads)? Why are they using flip to change number of heads? At what point the code without flip variable fails?
- I noticed similar thing in the problem multiple of 3 . There also coders have used an extra variable.
p.s. Please answer without using lazy propagations. I haven’t understood that properly yet. And I believe every problem that uses lazy propagation can also be solved without it (may get TLE but answer will be correct).