I have a 1-indexed array of positive integers, and I want to make several queries to it, all in the form, 'what is the sum of the largest x integers in the subarray 1 to y inclusive?' This array is not sorted and has no particular order.
x and y are not constant and can change between queries. Note: Input to all of these is guaranteed and I don't need to check for input. Time limit is 1 second (about 100 million operations is fine) Note 2: Queries can be offline.
Right now, I'm able to solve this in O(N log N) per query or O(QNlogN) overall just by sorting the whole array while keeping the indices, then taking the first x integers that have indices <= y. However, since I have a lot of queries, this is unfortunately too slow. (Bounds are up to 100,000 for x, y, N and Q, where N is the number of elements in the subarray and Q is the number of queries.)
Code for the too-slow priority_queue solution:
int n; scanf("%d", &n);
priority_queue<pair<int, int>> pq;
for (int i = 1; i <= n; i++) { // scan in the array and init priority queue
int a; scanf("%d", &a);
pq.push({a, i});
}
for (int i = 0; i < q; i++) {
int x, y; scanf("%d %d", &x, &y);
priority_queue<pair<int, int>> temp = pq;
int c = 0, ans = 0;
while (c < x) {
// if the element is not in the desired subarray, remove it
while (temp.top().second > y) temp.pop();
// element has been found
c++;
ans += temp.top().first*2;
temp.pop();
}
printf("%d\n", ans);
}
Is there an efficient way to do this, possibly in O(Q) or O(Q log x) time?
Googling has turned up no answer. I've searched SO (and CS too), and have found nothing similar. Everything I have found has either been on maximum contiguous subarray sum, or maximum sum in a sorted array. I have also looked in an algorithmics book and found nothing.
Partial-sort (see here) does not work, as it is too slow (using it would be O(QNlogN) in worst-case.