Add on interval, Query for number of elements less than val

Question

We have an array of numbers and we are supposed to do the following queries on it:

1. Add number x to all elements on the subarray with indices [ L, R ] of the array.
2. Query for number of elements less than number x of the whole array.

Note that x is given in each query and is not fixed.

I have a solution with time complexity $O(q \cdot log(n) \cdot \sqrt n)$ where $n$ is the size of the array and $q$ is the number of the queries (Storing sorted subarray in each block). However for constraints $n, q < 1e5$ with time limit of 2 seconds this is not efficient enough. So how to solve it on these constraints?

The only constraint is that the solution should work for 2 seconds when $n, q < 1e5$ and you can answer queries offline. Total complexity should fit in the constraints and the complexity for each query is not important.

Answer 1

Decompose the array to blocks of size $T = \sqrt{n \cdot log(n)}$ and Store the sorted corresponding subarray in each block. For each block $k$ store variable $bound[k]$ which is the number added to the whole subarray of the block. For the second query iterate over blocks and use binary search over $x - bound[k]$ on $k$th block. Time complexity would be $O(\frac n T log(T)) = O(\frac{n \cdot log(n)}{\sqrt{n \cdot log(n)}}) = O(\sqrt{n \cdot log(n)})$.

For updating queries, for each block $k$ that it's subarray is completely in the interval [ L, R ] update $bound[k]$ to $bound[k] + x$. Now we have at most two blocks which are modified but their subarray are not completely in the query interval. Iterate over the modified elements and update them by $x$. Now in each of those blocks you have two sorted arrays (modified and unmodified elements) and you are trying to merge them into one. This can be done in linear time, so rebuilding those two blocks takes $O(T)$. This way time complexity of each update query would be $O(\frac n T + T) = O(\sqrt{n \cdot log(n)})$.

Total complexity: $O((n + q)\sqrt{n\cdot log(n)})$.