Square root Decomposition

general
, ,
1

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 :slight_smile:

2

Square root decomposition is a great way to deal with range queries. This geeksforgeeks article explains it very well:

This video by @gkcs is very easy to understand:

2 Likes
3

how to write on a new line?
Pressing enter doesn’t seem to work :confused:

4

Press enter two times :slight_smile:

3 Likes
5

Welcome to codechef @abdullah768 . It took me 15 days to figure that thing out XD

1 Like
6

That worked, Thanks.

7

Square root decomposition is a concept explained by Sergey kulik as well.

I saw it once after last years Snackdown…

Video link:https://m.youtube.com/watch?v=VGq6w9TlJBY

1 Like
8

Here is the link which explain Sqrt Root Decompostion nicely.

http://www.infoarena.ro/blog/square-root-trick

Just read the “Range Sum” part.

Next go through the blog post of (@anudeep2011) https://blog.anudeep2011.com/mos-algorithm/ which explain query square root decomposition.

Thanks

1 Like
9

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.

good luck

10

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

1 Like