Square Root Decomposition with Code
Gentle introduction to Square Root Decomposition.
implementation of the idea discussed in the video: https://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?