Auto comment: topic has been updated by Sanjit-OP (previous revision, new revision, compare).

Here's an alternate approach using Mo's algorithm + sqrt decomposition:

1) Coordinate compress the values of array $$$A$$$ so that they lie in the range $$$[0, n-1]$$$

2) Sort the queries based on Mo's comparator.

3) Create 2 sqrt decomposition arrays $$$cnt[blocksize]$$$ and $$$sum[blocksize]$$$, where $$$blocksize = \sqrt{n}$$$. $$$cnt$$$ would store the count of elements that lie within a given block and $$$sum$$$ would store the sum of values (sum of the original values, not the coordinate compressed ones) that lie within a given block.

4) Create an array $$$cnt2[n]$$$, where $$$cnt2_i$$$ = no.of elements with compressed value $$$i$$$ (we will update this array in the add( ) and remove( ) functions of Mo's algorithm).

5) Let's say we want to add an element with compressed value $$$x$$$ and original value $$$y$$$ in Mo's algorithm. We will do the following operations:

add 1 to $$$cnt_{x / blocksize}$$$

add y to $$$sum_{x / blocksize}$$$

add 1 to $$$cnt2_x$$$

Do the opposite in the remove( ) function

6) Now that these 3 arrays reflect the range $$$[l, r]$$$, we are going to answer the current query.

Iterate from $$$0$$$ to $$$n-1$$$, incrementing $$$i$$$ by $$$blocksize$$$. Let the count of all elements in range $$$[0, i - 1] = currcnt$$$

If $$$currcnt + cnt_{i / blocksize} < k$$$, then increment $$$currcnt$$$ by $$$cnt_{i / blocksize}$$$ and add $$$sum_{i / blocksize}$$$ to the answer.

If $$$currcnt + cnt_{i / blocksize} \geq k$$$, then the greatest element that we consider in our answer should lie within this block. Iterate from $$$i$$$ to $$$n-1$$$ until $$$currcnt \geq k$$$ and keep adding the elements that you consider to the answer.

Time complexity: $$$O((n + q)\sqrt{n})$$$

You can solve using modified Fenwick tree
https://ideone.com/GjlHbl
This is rough code i will complete working code later , but you can definitely understand from this.

https://ideone.com/5x16ud this is general fenwick tree code to find top K sums.

Basically algorithm would be

for i = n to 1: 
     add_fenwick(a_i)
     solve queries whose l = i 

In this the main issue was in Fenwick we can find k top sums but that would for the range [i,n)
But we need for [i,j]

So i modified Fenwick from storing point sums to store prefix sums. So when we perform bit[i] += x

We will do instead bit[i].push_back(i,x)

As we know we are pushing i in decremental order, we can binary search on node to get sum only for r <= j

So Fenwick tree update complexity would be log and query complexity would be (log n)^2 Also as we care only about order while finding top k, i compressed the values before.like top K frequency.

net complexity: Q * (log n)^2 + nlogn

Persistent seg tree, online queries in O(log(max value)) time&space https://ideone.com/yjwDSV

resource to learn technique: https://cp-algorithms.com/data_structures/segment_tree.html#finding-the-k-th-smallest-number-in-a-range

You can do it online in log(A) per query with wavelet trees, where A is the largest integer in the array.

code

You can get O((n+q)logn) with merge sort tree and fractional cascading after doing value compression. Another solution is to make a persistent segment tree or a wavelet tree

Use a chairman tree(persistent segment tree) can solve this problem in $$$O(n \log n)$$$ online, but with a $$$O(n \log n)$$$ 's memory.

2 PST's.

One to find the k-th smallest (you can also use wavelet)

Another one to find the sum of elements in range smaller than that value. (version i can store elements smaller than the ith element. (or 0 otherwise)) (Will be just range sum) (Apply coordinate compression if needed.)

Complexity: O(N log N)