Square Root Decomposition with Code

Gentle introduction to Square Root Decomposition.
implementation of the idea discussed in the video: ideone.com/eg4y3S
To solve the problem of answering range queries on an Array A[1..N].
Queries are of two types:
1. find function F applied on the range [L,R]. F can be sum, min, max or wide range of other functions.
2. point update. set A[i] = new_value V.
Algorithm:
1. Break Array A into X smaller chunks each with Y elements.
2. Find F applied over each chunk individually.
Why exactly root N chunks each with root N elements?

[@dontony7071]

Bhaiya for numbers which are primes like 1e9+7 or numbers which are not perfect squared like 3^9 will this method work?

[@AlgosWithKartik]

Yes it will. Imagine N the size of array is not a perfect square. There are two things you can do: 1. Add some extra elements to the array (equal to identity element, 0 incase of sum queries) to make the size a perfect square. 2. Make ceil(root(N)) chunks with each chunk having exactly ceil(root(N)) elements except for the last chunk which will have fewer elements and it's okay.

[@dontony7071]

Got it bhaiya.Thanks for replying🙂.

[@Asdfgadv33423]

@@AlgosWithKartik Hello. How hard is it to get an internship for a big company while being at university? Ty! edit: And if you know, can you give me some advice about it? What to work on, what types of problems should i solve, any advice would be great!

[@hardikraj9469]

Thanks, I wanted an implementation of square root decomposition for a long time.

[@ankitpandey3724]

It really feels bad to see that the frequency of video uploads has reduced. But its understandable you have to work life too. Thanks a lot though 🎉🎉🎉.

[@AlgosWithKartik]

Frequency might be low but I'll keep posting useful content and trying my best to add value :)

[@ankitpandey3724]

@@AlgosWithKartik that's all we need. Thanks a lot bhaiya.

[@girishgarg2816]

Kya bawal chiz bana diye ho. Maza agaya

[@mahbubulalamsabuj373]

bhai you are amazing.keep doing this for us please

[@AnkitJosh]

Bhai mauj kardi. Tum toh bade heavy explainer ho bhai

[@abhijeetbasfore6816]

What about Mo's algorithm?

[@subhashgupta7783]

Very important concept kartik bhaiya ❤️

[@subhashgupta7783]

with too many applications *

[@AyushGupta-mm4jg]

Thanks for the videos :)

[@saumilkapadia88]

Lovely explanation!

[@bawabigballer]

what an explanation. amazing

[@girishgarg2816]

Bhaiya expected value part 2 kab aayegi?

[@AlgosWithKartik]

Abhi bandwidth kam h and time milne prr focussing on range query series. Will try ki expected value bhi jaldi continue krru :)

[@girishgarg2816]

@@AlgosWithKartik Okay. I have been binge watching your videos. Gem content.

[@vijaykumarlokhande1607]

precise

[@sahilbazard4273]

Please continue for segment and fenwick trees🙌

[@jimjam9026]

Hello bro your explanations are really great ( probably finest in all of youtube ) please make vedioes on segment trees and Fenwick trees also.

[@abdullasulfikkar5282]

thank you bhaiya

[@shubheshtiwari8525]

bawaal ekdum

[@codewithdev1375]

The best explanation, i love your teaching bro . Please do make videos on problem solving using these methods it will give us much better understanding.

[@bodduaravind5843]

Sir please start graph series