Is it possible to solve this problem using SQRT-decomposition ?
0.5 second is a very tight limit and in-spite of minor optimizations and fast I/O my code having complexity of O (N * sqrt (N)) is getting TLE on test case 17.  I am just curious about the possibility.

It is actually a very tough problem when you're using a segments tree, so I do not think that using a SQRT-decomposition is a very good idea. For me the key was to implement the segments tree with iterative update procedure.