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.
For each query use a binary search over the answer.
Determine the number of elements in each tree node having prefix_sum < answer value.
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 :)
