Just Another Range Query

If we ignore input constraints, this is a classic segment tree problem. We need Nlog(N) space and run time to build a segment tree of size N, which is huge when N is 10^9. This is the only challenge in this problem.

But, do we really need to preprocess the segment tree? What if we build the segment tree while answering queries?

We will create a node of the segment tree only when we need to update it. We won’t create a node if it is never updated. Then how will we get the information of those nodes which are not created? In this problem, we can find those information using the n(n+1)/2 formula.

Now we need to explore or create at most 2log(N) nodes while updating or querying in a segment tree. Since we have Q queries, we need to create and explore at most 2Qlog(N) nodes, which is efficient enough in terms of space and run time.

An alternate solution is compressing the array. We can store and sort the values of query indexes in an array. Then we can build a segment tree where each index will contain information of several consecutive elements of the given array.

Suppose after sorting query indexes we have: 1, 5, 6, 9, 12. Now we can build a segment tree where index 1 will represent the block [1,1], index 2 will represent the block [2,4], index 3 will represent the block [5,5] and so on.

In this approach, we will need Qlog(Q) run time and space to build the segment tree and Qlog(Q) time to answer queries.