Given an array of integers and a range find the count of subarrays whose sum lies in the given range. Do so in less than O(n^2) complexity.

# | User | Rating |
---|---|---|

1 | tourist | 3581 |

2 | OO0OOO00O0OOO0O0…O | 3264 |

3 | mnbvmar | 3246 |

4 | LHiC | 3183 |

5 | Um_nik | 3176 |

6 | Petr | 3161 |

7 | Radewoosh | 3128 |

8 | CongLingDanPaiSh…5 | 3116 |

9 | ainta | 3115 |

9 | ko_osaga | 3115 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 190 |

2 | Errichto | 166 |

3 | rng_58 | 161 |

4 | tourist | 158 |

5 | Vovuh | 150 |

5 | Um_nik | 150 |

7 | Petr | 149 |

7 | Swistakk | 149 |

9 | 300iq | 148 |

10 | PikMike | 147 |

10 | neal | 147 |

Given an array of integers and a range find the count of subarrays whose sum lies in the given range. Do so in less than O(n^2) complexity.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2018 16:17:50 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

let us call the range [

l,r] build the prefix sum array for the given array, let us call itB(B[0]=0 for empty prefix)now

B[i] -B[j] where 0 ≤j<igives all the sums of subarrays that end in

i^{th}elementSo, in order for the sum of subarray [

j+ 1...i] to be betweenlandrthe following should be true:l≤B[i] -B[j] ≤r=>

l-B[i] ≤ -B[j] ≤r-B[i]=>

B[i] -l≥B[j] ≥B[i] -rso for each

B[i], we should find the number ofB[j] s that are in the previous range andj<i, which is done in a segment treetotal complexity:

O(nlogn)NOTEIf the values are all positive you can use binary search forO(nlogn)How could segment tree be used to find the possible values of j?

Array

C, C[i] is the number of B[j]'s which are equal to iYou need a segment tree to perform 2 types of queries:

1) add 1 to C[x]

2) get the sum of C[x] : s<=x<=e

So for each B[i] you query for the sum of C[x] between B[i]-r and B[i]-l Then you add 1 to C[B[i]]

B[i] can be negative ..how it is possible to store in array?

Then compress the values

I was trying to solve this question. I tried to compress the values. But it is giving WA. Here is the code. Please help me.

You will have at most N+2 different values (Including L and R), compress them.

Can you please have a glance at my code?

For each B[i], I have to put B[i]-l and B[i]-r. I have to compress n*2*n values.

Were you able to solve that question ? If yes, can you please share the code? I am also getting W.A.

Yes, I solved it Here is the code

If the values are all positive you can solve in

O(N) using only 3 pointers.Note:You can also solve inO(NlogN) without segment tree, just using divide-and-conquer idea.Could you elaborate how divide and conquer could be used?

B— partial sum,B[0] = 0.Now we are going to split our verctor

ainto 2 parts with sizeN/ 2 each.2 cases are possible:

1)

l,r<N/ 2 orl,r>N/ 2: We can find the answer recursively for the left part and for the right part.2)

l<N/ 2 andr>N/ 2: We can find the answer inO(N) using 3 pointers but only if the left part sorted and the right part sorted too. But you can maintain these parts sorted by using merge sort algorithm.The algorithm is very similar to the algorithm for counting inversions in

O(NlogN) time. You can find the explanation on coursera: linkFor segment tree , Is the time complexity is (n*log(sum of all array elements)) ? correct me if i am wrong.

Wrong? You didn't state anything.

As JoudZouzou said ,when we use segment tree to solve the problem total complexity: O(nlogn) but here the logn is not the size of input but it is log of the sum of the array elements

Your solution is quite beautiful :)

Could you please provide such type of problem for more practice? :)

Note: This works only for positive integers.

I think following expression may help: (For a range [L,R])

For finding required number of subarrays refer this: Subarrays with sum less than k