How to find sum of maximum K elements in range in array

Recently, I came up to the following problem:

Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for given range $[l, r]$ we should find sum of the $k$ maximum elements over all $A_i$ such that $l \leq i \leq r$.

Trivial solution would be to sort all values in the range and iterate over the k biggest elements, however this has complexity $O(QN\log N)$. After some searching on the internet, I found out that this can be solved by segment trees, however I couldn't think of proper use of segment trees for this problem.

Is it possible to solve this problem in complexity better than $O(QN\log N)$

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices.

Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.

With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(n\log n)$ preprocessing and $O(\log n)$ time per query.

StackExchange Computer Science Q#109579, answer score: 5