How to solve this problem for large data set . I saw the code of other contestants it seems like they are using divide and conq but i am not able to fully understand it . asked 06 Mar '18, 18:38

Since the sum of every subarray is just the difference of two prefix sums, we can create two polynomials corresponding to the prefix sums and their negative. Let the prefix sums of the array be s1,s2,...sn. P1 = x^s1 + x^s2 + ... + x^sn The coefficient of x^i in P1*P2 will be the number of subarrays having sum 'i'. However, since we can't deal with negative powers, we will multiply p2 with x^S (S>=sn). Now, the coefficient of x^i will represent the number of subarrays having sum iS. We will only take the coefficients corresponding to positive values ie. iS >0 or i>S. We can store these counts in an array and binary search for each query. The complexity of this solution will be O(AlogA + QLogA) where A = 100*N. answered 08 Mar '18, 17:54
That is a neat solution, probably the intended one.
(08 Mar '18, 20:06)
Or maybe not... you can handle much larger number of queries with this approach.
(08 Mar '18, 20:33)
Probably a much better solution than intended :)
(08 Mar '18, 20:35)
@meooow's solution with two pointers instead of binary search (for counting subarrays with sum <=x) will be faster, for Q=20. That might have been the intended solution.
(09 Mar '18, 12:36)

I think we can do this using divide an conquer and fft(convolution). Lets say we have arr= 1 4 3 6 Now we divide this into two halves 1 4 and 3 6 To calculate the the sum of range [l,r] where l is in left part and r in right we would need to merge the suffix of left part with prefix of right part. Now calculate the suffix sum for 1 4 which is 5 4 and prefix sum for 3 6 which is 3 9 So now lets merge so (5+3),(5+9),(4+3),(4+9) So these sums are possible if l is in left and r in right halve. This can be done using fft. Let us express left halve as x^4 + x^5 and right as x^3 +x^9. Do their multiplication,the coefficient represents the occurrence.(just keep a global frequecy map and update accordingly) Now similarly calculate for left and right part recursively. Complexity aroung nlog^2n answered 07 Mar '18, 01:25
Thanks @vivek_1998299 for the explanation i dont understand the fft part "Do their multiplication,the coefficient represents the occurrence.(just keep a global frequecy map and update accordingly)"..
(07 Mar '18, 19:18)
See the possible sums should be (5+3),(5+9),(4+3),(4+9) Now (x^5 + x^4)*(x^3 + x^9)= x^(5+3) + x^(5+9) + x^(4+3) + x^(4+9) As u can see coefficents of multiplication is 1 for all terms,ie (5+3),(5+9),(4+3),(4+9) occured once. (The coefficient of x^y represents the number of occurence of y) Now this multiplication can done faster using fft.
(07 Mar '18, 19:21)
@vivek_1998299 but after creating N(N+1) its sorted will this work for sorted array(N(N+1)) too?
(07 Mar '18, 19:29)
Yeah ,the whole reason for doing this divide and conquer and fft was to create a frequency map of sums of n(n+1)/2 subarrays.If u see then only n100 values can be possible.After constructing frequency map We can then easily answer any query.
(07 Mar '18, 20:41)
I mean lets say frequncy map is: 1  2 times 3  1 time I want [1,3] which is 1 * 2 + 3 * 1 ,(i mean O(n * 100)) (Or rather preprocess to answer in O(logn) )
(07 Mar '18, 20:44)
@vivek_1998299 can you explain your approach a bit more? Also if you can share some working code that would be great.
(08 Mar '18, 02:16)
Ohk,so put forward simply,first we calculate sum of all subarrays[l,r] whose l lies in left ,r lies in right part there are about n^2/4 such subarrays.Now the only subaarays that remain are the one whose [l,r] both lies in left part ,or both lies in right part.So we could do this recursively over left and right part.And for a particular level of recursion tree the complexity is O(nlogn) (for fft merging),there are logN levels so total complexity O(nlogn^2)
(08 Mar '18, 09:48)
The recurrence relation is T(n)=2T(n/2)+O(nlogn)
(08 Mar '18, 09:53)
showing 5 of 8
show all

Can you provide a link to any solution that uses divide and conquer? I know a way to solve this but in a different way.
@meoooow If possible can u explain your method?
@meooow u can see the solution in the rank list !