Hey, I want to solve this problem: Given array a of length n handle these queries online (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 <= 10^6$$$ , $$$q <= 10^6$$$ (q is number of queries), the array has only positive integers ($$$a_i <= 10^9$$$))
I know it is possible to do using Wavelet tree.
You can do it using presistent segment tree.
I don't see how it's possible to solve it faster than $$$O(\log^2 n)$$$ with wavelet tree. Are you sure it's doable?