如何从l到r找到排序子数组的第k个元素的总和？

Question

问题:
我们给出了一个A[]大小的数组N.现在我们给出了Q查询,每个查询由三个整数组成,l,r,k其中:

1<=l<=r<=N
1<=k<=(r-l+1)
1<=N,Q<=10^5

现在,我们要找出高达的总和k从分类子阵列的元素l来r.
例如:
让N=6和数组元素是5,1,7,4,6,3
和Q=1哪里l,r,k一样2,5,3.
然后从子阵列index 2 to index 5是{1,7,4,6}
排序它变为如后{1,4,6,7} 所以总结高达k=3项等于(1+4+6)=11
这样,请回答是11.

我已经尝试过使用每个子数组的排序然后求和,Q*N*log(N)在最坏的情况下需要时间复杂度.
请帮助在时间复杂度内找到比Q*N最坏情况更好的解决方案.

Answer 1

一种方法是使用合并排序进行预处理，并修改为保留所有排序的中间结果的副本。

此预处理需要 O(nlogn)。

假设我们从 32 个元素开始。我们现在将有：

• 16 个排序的 2 元素列表
• 8 个排序的 4 个元素列表
• 4 个已排序的 8 个元素列表
• 2 个已排序的 16 个元素列表
• 1 已排序的 32 个元素列表。

我们还可以在 O(nlogn) 中预先计算每个列表的前缀和。

然后，当面对从 l 到 r 的查询时，我们可以识别预处理列表的 log(n)，这些列表一起将覆盖从 l 到 r 的所有元素。

然后，我们可以使用二分搜索来查找值，使得所识别的列表中正好有 k 个较小的元素，并使用前缀和来计算总和。