I recently learned Segment Trees and applied it to the question: FLIPCOIN.
I am getting TLE in my solution. Here is a link to my solution. Please tell me why am I getting TLE and how to remove it.
knowledge of segment tree is not enough to solve this,lazy propagation is also required.
For this question, you have to use Segment Tree with lazy propagation.
Your code uses a simple Segment Tree without lazy propagation and hence gets a TLE.
In lazy propagation we mark the nodes that needs to be updated, but update them only when required. This saves time and makes this approach faster.
The following link has a nice blog about Segment Trees with lazy propagation.
You can refer to my code for the solution in the following link.
Thanks…Can you please point out my mistake in code?
Thanks for the help