What is Square root Decomposition? I was reading editorial of a problem on hackerrank and came acroos this term. I tried searching on google, read various forums but couldn't understand how this could optimise a code. Can anyone please provide a simple explanation of this problem and give a clear, easy and intuitive code for the same? Thanks in advance :) asked 03 May '17, 14:34

Square root decomposition is a great way to deal with range queries. This geeksforgeeks article explains it very well: http://www.geeksforgeeks.org/mosalgorithmquerysquarerootdecompositionset1introduction/ This video by @gkcs is very easy to understand: answered 03 May '17, 14:38
how to write on a new line? Pressing enter doesn't seem to work :/
(03 May '17, 14:39)
3
Press enter two times :)
(03 May '17, 14:40)
1
Welcome to codechef @abdullah768 . It took me 15 days to figure that thing out XD
(03 May '17, 14:41)
That worked, Thanks.
(03 May '17, 14:41)

Square root decomposition is a concept explained by Sergey kulik as well. answered 03 May '17, 14:44

Here is the link which explain Sqrt Root Decompostion nicely. http://www.infoarena.ro/blog/squareroottrick Just read the "Range Sum" part. Next go through the blog post of (@anudeep2011) https://blog.anudeep2011.com/mosalgorithm/ which explain query square root decomposition. Thanks answered 03 May '17, 14:48

can someone please figure out why am i getting wrong answer for my submission in this test case or may be , suggest some new logic for this question , Question link  https://www.codechef.com/problems/GIFTCHEF Solution link  https://www.codechef.com/viewsolution/13428580 answered 03 May '17, 21:32

This is by far the best after watching gkcs video . Here's you can see how to implement this and its very proof as well. https://www.hackerearth.com/practice/notes/mosalgorithm/ good luck answered 03 May '17, 15:36
