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:
Constraints :-
1<=N,Q<=2*10^5,
1<=K<=10^3,
1<=A[i],Y<=10^9,
0<=L<=R<=N-1
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.
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)
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,
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).
