Sum of K smallest element in range queries.

Revision en2, by Sanjit-OP, 2022-05-25 10:30:43

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].

Thanks in advance :)

Tags subarray, prefix sum, segment tree, persistent segment trees


  Rev. Lang. By When Δ Comment
en4 English Sanjit-OP 2022-05-25 14:05:17 496 Tiny change: 'und search).\n\nTime' -> 'und search in each node).\n\nTime'
en3 English Sanjit-OP 2022-05-25 10:38:11 445 Tiny change: ' log(N) = Segment tre' -> ' log(N) = Iterating over segment tre'
en2 English Sanjit-OP 2022-05-25 10:30:43 277
en1 English Sanjit-OP 2022-05-25 09:35:24 288 Initial revision (published)