Binary search

Please help me understanding the approach of the given problem.
Just not able to understand how sorting on prefix sum helps here.

For an array A_i we denote the prefix sums as,

P_i=\sum_{j=1}^NA_i

So it’s a very trivial observation that

P_r-P_{l-1}=\sum_{i=l}^rA_i

We can conclude that if we take the difference of any 2 prefix sums, we’ll get the summation of elements of some subarray. But since we’re only interested in the number of subarrays and only the absolute sum is all that matters, we can sort all the elements in the prefix array. By absolute value I mean,
suppose in the sorted sequence P_r some before P_{l-1} so if we take the difference.

P_{l-1}-P_r=-\sum_{i=l}^rA_i

But absolute value remains the same hence we’re good.
For the rest of the part, we’re just doing some trivial contribution counting for the rest of the part, which I think you might’ve already understood though feel free to ask anything if you didn’t get the idea.

2 Likes

Thank u very much @cubefreak777 i got u… Damn such simple i wasn’t able to get this much… thanks again for the help…

1 Like