Hey, I want to solve this problem: Given array a of length n handle these queries (each query in O(logn))

-> l r k (input) which means output the sum of k largest numbers on segment [l,r] in array a.

($$$n \lt = 10^6$$$ , $$$q \lt = 10^6$$$ (q is number of queries), the array has only positive integers ($$$a_i \lt = 10^9$$$))

I know it is possible to do using Wavelet tree.