Hello… I am learning about segment tree and lazy propagation and I found this problem. After searching about this problem I came to know that it can be solve using SEG-Tree + Lazy Propagation, but can you please help in making a segment tree solution, actually I wanna do it by using Seg-Tree(I know it wouldn’t pass test cases but still…). Till now I came up with this approach, but its not working(I think the update part).

done with just seg-T [here][1]
[1]: http://ideone.com/JFFws1


I have corrected the update part. There were a few bugs in your code due to which it was giving run-time error. I wasn’t able to get your approach for the problem though.

I suggest you to solve some more simple problems on segment-trees first so that you are fluent in writing the build and query part.


  1. Tutorial-1

  2. Tutorial-2

  3. Tutorial-3

Try to understand how a segment tree behaves because direct segment tree questions are rare! Once you get a thorough understanding, solve these 2 problems:

  1. Horrible Queries

  2. Chefhill

These 2 problems are just based on implementation if you understand segment trees.