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

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

I saw it once after last years Snackdown…

Video link:- YouTube

3 Likes
4

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
5

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

6

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 - GIFTCHEF Problem - CodeChef

Solution link - CodeChef: Practical coding for everyone

1 Like
7

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

8

Press enter two times :slight_smile:

3 Likes
9

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

1 Like
10

That worked, Thanks.