Sum of K smallest element in range queries.

Revision en4, by Sanjit-OP, 2022-05-25 14:05:17

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:

  1. Build a merge-sort segment tree and a prefix-sum segment tree.

  2. For each query do a binary search over an integer (say V).

  3. Now count the elements in the merge-sort seg tree with values <= V and also return the prefix sum of such elements.

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

  5. 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 :)

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)