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).

link->http://ideone.com/jPUedW

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.

Tutorial:

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:

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

6 Likes