×

Square root Decomposition

 0 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 3★shraeyas 1.3k●2●6●18 accept rate: 10%

 2 Square root decomposition is a great way to deal with range queries. This geeksforgeeks article explains it very well: http://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/ This video by @gkcs is very easy to understand: https://www.youtube.com/watch?v=hqaRYgsLpUI answered 03 May '17, 14:38 2.4k●4●20 accept rate: 17% 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) shraeyas3★ 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)
 1 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 answered 03 May '17, 14:44 904●10 accept rate: 9%
 1 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 answered 03 May '17, 14:48 5★vidyut_1 144●4 accept rate: 20%
 1 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 2★ho_dor 31●1 accept rate: 0%
 0 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/mos-algorithm/ good luck answered 03 May '17, 15:36 3★ankush23 31●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×78
×9
×1

question asked: 03 May '17, 14:34

question was seen: 2,045 times

last updated: 03 May '17, 21:32