Question : “https://www.spoj.com/problems/KQUERY2/” [TIme limit 1Sec]
Similar Question : “https://www.spoj.com/problems/RACETIME/”[Time Limit 2 Sec Approx]
Now when I solve KQUERY2
with same solution as RACETIME
[here] gives me TLE as KQUERY2 has very very strict time limit
Below are the solution for KQUERY2(main issue only with update query)

Using SQRT decomposition , per update — \sqrt{n} + \sqrt{n}log( \sqrt{n}) [ TLE , HERE]

Using SQRT decomposition , per update in — log(\sqrt{n}) + \sqrt{n}log( \sqrt{n}) [ TLE , HERE]

Using SQRT decomposition + Binary Index Tree , per update — \log(\sqrt{n}) [ block size \sqrt{n} , TLE , HERE]

Using SQRT decomposition + Binary Index Tree , per update — \log(\sqrt{n}) [ block size 3\sqrt{n} , AC , HERE]