Question : “SPOJ.com - Problem KQUERY2” [TIme limit 1Sec]
Similar Question : “SPOJ.com - Problem 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]