Awesome Question on BIT+SQRT Deomposition [KQUERY2 , SPOJ]

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

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

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

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

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

2 Likes

This post was flagged by the community and is temporarily hidden.

Why do u hate segment tree?

3 Likes

I think it’s harder than other approaches so.