PROBLEM LINKS:Author: sikander_nsit DIFFICULTY:MEDIUM PROBLEM:In the problem we had to find the sum of the smallest k elements in the given array range. EXPLANATION:Brute force solution would not work because of the constraints. Segment tree can be used for this. Each node of the segment tree will consist of two arrays : first is the list of elements in the range in sorted order and the second stores the cumulative sum. For every query we can find a list of S sorted arrays such that their union is the given range in query [L,R].
When you get to the point where you only have one element per array (or 0), make a new array of size n with those data, sort, and calculate the sum of first k elements. Because you're always guaranteed to remove at least half of one array, in S iterations, you'll get rid of half the elements. That means there are S log k iterations. Each iteration is of order S log k (due to the binary searches), so the whole thing is S^2 (log k)^2 in worst case. But the actual performance would be much better than the worst case. AUTHOR'S SOLUTION:Author's solution can be found here.
This question is marked "community wiki".
asked 11 Feb '14, 04:37

One more way of doing this is using a persistent segment tree. answered 11 Feb '14, 11:34

" so the whole thing is S^2 (log k)^2 in worst case. But the actual performance would be much better than the worst case." can anyone explain this why this statements holds? because i followed it and my solution gets accepted in 0.19sec but i am expecting TLE instead... answered 27 Jun '17, 18:21
