Hi CodeForces, in this topic i want to tell what sqrt decomposition is, give you an example, and give some problems which can be solved by sqrt.

The whole thing that sqrt is, is to reduce complexity by divide queries and get better complexity. e.g. I have an algorithm with O(N^2) complexity and another algorithm with O(k.N + N^2 / k) complexity where k is size of blocks i made, then i can have O(N.sqrt(N)) algorithm with set k to sqrt(N).

We'll solve a problem to clarify. The problem is this:

you're given an array A with n elements and q queries with 2 types: "? l r" you have to print sum of values between l(inclusive) and r(exclusive) ( [l, r) ) "+ l r x" you have to increase all elements between l and r by x. and n <= 1e5, q <= 1e5. (by the way you can solve this problem using segment tree or fenwick tree with more ease.)

let's consider A as n/k consecutive bucket with each bucket (except of the last) has k elements. then we can do so: if we want to change/process a full bucket, then we'll change a variable referencing to this bucket and if not, we'll change elements one by one. so in each query we'll use at most 2 incomplete buckets and at most n/k complete buckets, so the complexity will be from O(q.n/k + q.k). since product of q.n/k and q.k is constant, the minimum sum is reached when q.n/k = q.k. thus k = sqrt(n) and the complexity is from O(n.sqrt(n)).

there is a sample code that do so here.

read 342E - Xenia and Tree, first think about how you can solve it and then go ahead.

think about how we can solve if we could use O(q^2) for example.

now, let's try to improve the algorithm by partition queries in k-sized groups and see how this can help us.

so now we have an algorithm from O(n.q/k + qk), thus how we proved before, k = sqrt(n) and the algorithm is from O(q.sqrt(n)).

here are some other problems that can be solved by sqrt decomposition. 44C - Holidays, 13E - Holes, 86D - Powerful array, 398D - Instant Messanger and 455D - Serega and Fun.

In the end, how you saw in problems there's not a single type problems which sqrt can solve. another thing that you should notice, is what your bucket sizes should not be sqrt always, think of you have an O(k + n.log/k) algorithm like we proved before, the minimum is when k^2 = n.log or k = sqrt(n.log).