问题:
我们给出了一个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最坏情况更好的解决方案.