Square Root Decomposition Help!

Can anyone explain me how to solve this question using Square Root Decomposition

You have an array of N integers and Q queries on this array. There are two types of queries:

  1. 1 L R – count the numbers divisible by K in range [L, R].
  2. 2 L R Y – add Y to all numbers in range [L, R].

Constraints :-


and is there any other technique to solve such queries??
Thanks in Advance

As far as i know, this is a standard question of segment tree with lazy propagation.

1 Like

Following solution is quite straightforward. Let me know if you need detailed exp.
We can achieve these complexities
Preprocessing = O(n)
for Query 1,O(n^1/2)
for Query 2, O(n^1/2)

1 Like


Just make an update function and iterate over blocks and update their sum in O(1) which in worst case will go up to sqrt(N) if you iterate over all such blocks.Same goes with sum query.
So time complexity will be as mentioned by @gagan86nagpal

It would be great if you explain how to achieve both operations in O(sqrt(n))

Divide whole arrays in root(n) blocks.
For each block, create an array of size k. This will hold the count of numbers in the respective block for a modulus residue class (%k).
Eg. Let block contains 1 2 3 4 6 and k = 3, your array will be {2, 2, 1}.

For query 2:
l,r will span for some complete blocks and at max 2 partial blocks (leftmost and righmost blocks). For partial blocks, you should update your arr[] naively. For complete box, just maintain a shift variable (this represents how your arr[] values will shift).

Now, For query 1:
l,r will again span. For a complete block, ans is arr[0 ± shiftForThisBlock] and for partial blocks use brute force.

For both queries, Complete blocks are atmax sqrt(n) and partial nodes will be less than sqrt(n).
This gives sqrt(n) complexity,

1 Like

I also tried the same question given on hacker earth using sqrt decomposition but it is giving TLE on all test cases except one

Better Use segment tree with lazy updates to solve this question.Time Complexity for Updates And sum will be O(logn).

@aman_robotics thanks for the link

@gagan86nagpal thanks for the explanation :slight_smile:

@naveen19991124 @s_anand98

can you tell how to do the updates with lazy tree??