533. Count of Range Sum

Given an array and a range [lower, upper], count the number of contiguous subarrays whose sum lies within [lower, upper] inclusive. Use prefix sums with a merge-sort or BIT counting approach. The input is JSON {nums, lower, upper}. Return the count.

Input: JSON {nums, lower, upper}.

Output: Integer — the number of qualifying range sums.

Examples

Input: {"nums":[-2,5,-1],"lower":-2,"upper":2}
Output: 3
Explanation: Three subarrays have sums in [-2,2].

Input: {"nums":[0],"lower":0,"upper":0}
Output: 1
Explanation: Single zero subarray.

Input: {"nums":[1,2,3],"lower":3,"upper":5}
Output: 3
Explanation: Subarrays summing within [3,5].

Constraints

• 1<=n<=10^5
• -2^31<=value<=2^31-1

Asked by