Sum of K smallest element in range queries.

Правка en2, от 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 :)

Теги subarray, prefix sum, segment tree, persistent segment trees

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Sanjit-OP 2022-05-25 14:05:17 496 Tiny change: 'und search).\n\nTime' -> 'und search in each node).\n\nTime'
en3 Английский Sanjit-OP 2022-05-25 10:38:11 445 Tiny change: ' log(N) = Segment tre' -> ' log(N) = Iterating over segment tre'
en2 Английский Sanjit-OP 2022-05-25 10:30:43 277
en1 Английский Sanjit-OP 2022-05-25 09:35:24 288 Initial revision (published)