Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Sum of K smallest element in range queries.

Revision en1, by Sanjit-OP, 2022-05-25 09:35:24

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

History

 
 
 
 
Revisions
 
 
  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)