**Author:** Abhishek Kanhar

**Tester:** Abhishek Sajwan

**Editorialist:** Abhishek Sajwan

## DIFFICULTY:

Medium

## PREREQUISITES:

FFT, Sqrt Decomposition

## EXPLANATION:

Key trick is to consider the arrays as polynomials. For example, the polynomial A becomes A[0]x^{0} + A[1]x^{1} + …. so on.

To execute queries of the first type, we can shift the array B to the corresponding index of array A that needs to be updated. For example, we have the query “1 4”, then we need to shift the polynomial B with x^{3} and then add the resulting polynomial to polynomial A.

But this solution will still take **O(N ^{2}log(N))**.

To make it more faster, we can split the queries into blocks of size **sqrt(Qlog(Q))**, and then update the array A at the end of each block.

Now we look at each block separately.

For queries of type 1 l, we now just store the indices l.

For queries of type 2 l r, we need the sum(l,r) of array A updated before this block and the sum of ranges array B according to the stored indices. All this can be done by pre-computing the presum values of arrays. The complexity of this operation is of the order of no. of stored indices which is **O(sqrt(Qlog(Q)))**.

At the end of each block, we update the array A according to the stored indices. For this we need the convolution of array B and the the stored indices. We create the polynomial for stored indices and then do the convolution. This if done by FFT or NTT(with larger modulo).

**Minor optmization** - Use NTT instead of FFT, calculate transform of B only once in the problem

**Expected Complexity - O(Nsqrt(Nlog(N)))**

Author’s Solution can be found here

Tester’s Solution can be found here