Hi, code forces, I have been getting haunted by this problem for a long time now.
Would you please help me to understand what data structure and approach are needed to solve this problem? This problem is not from any live contest.
Given an array A having N integers in the range [-1e8, 1e8] and Q queries each having 3 integers [L, R, K]. For each query, the task is to return the sum of K's smallest elements in the subarray A[L...R] where K = [1, R-L+1].
My approach:
Build a merge-sort segment tree and a prefix-sum segment tree.
For each query do a binary search over an integer (say V).
Now count the elements in the merge-sort seg tree with values <= V and also return the prefix sum of such elements.
Return a pair from step-3 {prefix_sum, C}, where prefix_sum denotes the sum of chosen elements and C denotes the count of chosen elements over binary-search value V.
If C < K then search for higher value V in binary search. Otherwise, the current answer sum of K's smallest element = prefix_sum + (C-K)*V (this also handles duplicates during upper_bound search in each node).
Time complexity: Q.log(X).log(N).log(N), where X is 1e15.
Q = Total queries
log(X) = Binary search over max answer limit.
log(N) = Iterating over segment tree nodes
log(N) = Upper_bound on prefix sum on each node.
Thanks in advance :)
