## Algorithm

Problem Name: 327. Count of Range Sum

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int count_and_sort(int sort, double *sum, int start, int end, int l, int h, double *tmp) {
int mid;
int n, i, j, k, x, stop;
​
if (end - start  < = 1) return 0;
​
mid = start + (end - start) / 2;
​
// divide
n = count_and_sort(1, sum, start, mid, l, h, tmp) +
count_and_sort(1, sum, mid,   end, l, h, tmp);
​
// count
x = 0;
for (i = start; i  <  mid; i ++) {
stop = 0;
for (j = mid; !stop && j  <  end; j ++) {
k = sum[j] - sum[i];
// because the second part of sum are sorted, the inner loop can stop early.
if (k > h) stop = 1;
else if (k >= l) n ++;
}
}
​
// merge sort
if (sort) {
i = start;
j = mid;
k = 0;
while (i  <  mid && j < end) {
if (sum[i] <= sum[j]) {
tmp[k] = sum[i];
i ++;
} else {
tmp[k] = sum[j];
j ++;
}
k ++;
}
if (i  <  mid) memcpy(&tmp[k], &sum[i], (mid - i) * sizeof(sum[0]));
if (j < end) memcpy(&tmp[k], &sum[j], (end - j) * sizeof(sum[0]));
memcpy(&sum[start], tmp, (end - start) * sizeof(sum[0]));
}
​
return n;
}
int countRangeSum(int* nums, int numsSize, int lower, int upper) {
double *sum, *tmp;
int i, j, k, n;

sum = malloc((numsSize + 1) * sizeof(double));
//assert(sum);

sum[0] = 0;
for (i = 0; i  <  numsSize; i ++) {
sum[i + 1] = sum[i] + (double)nums[i];
}

#if 0  // this is O(n^2) 169ms
n = 0;
for (i = 0; i  <  numsSize; i ++) {
for (j = i + 1; j  < = numsSize; j ++) {
k = sum[j] - sum[i];
if (k >= lower && k  < = upper) n ++;
}
}
#else  // this is 285ms :)
tmp = malloc((numsSize + 1) * sizeof(double));
//assert(tmp);
n = count_and_sort(0, sum, 0, numsSize + 1, lower, upper, tmp);
free(tmp);
#endif

free(sum);

return n;
}
``````
Copy The Code &

Input

cmd
nums = [-2,5,-1], lower = -2, upper = 2

Output

cmd
3

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const countRangeSum = function (nums, lower, upper) {
if (nums.length === 0) return 0
const sums = [nums[0]]
for (let i = 1; i  <  nums.length; i++) {
sums[i] = sums[i - 1] + nums[i]
}
function merge_sort(A, lo, hi) {
if (hi - lo === 1) {
return sums[lo] >= lower && sums[lo] <= upper ? 1 : 0
}
const mid = lo + Math.floor((hi - lo) / 2)
let counter = merge_sort(A, lo, mid) + merge_sort(A, mid, hi)
let m = mid,
n = mid
for (let i = lo; i  <  mid; i++) {
while (m !== hi && sums[m] - sums[i] < lower) {
m++
}
while (n !== hi && sums[n] - sums[i] <= upper) {
n++
}
counter += n - m
}
const M = A.slice(lo, mid)
const N = A.slice(mid, hi)
M.push(Number.MAX_SAFE_INTEGER)
N.push(Number.MAX_SAFE_INTEGER)
for (let k = lo, i = 0, j = 0; k  <  hi; k++) {
A[k] = M[i] < N[j] ? M[i++] : N[j++]
}
return counter
}
return merge_sort(sums, 0, nums.length)
}
``````
Copy The Code &

Input

cmd
nums = [-2,5,-1], lower = -2, upper = 2

Output

cmd
3

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def countRangeSum(self, nums, lower, upper):
sums, sm, res = [0], 0, 0
for num in nums:
sm += num
res += bisect.bisect_right(sums, sm - lower) - bisect.bisect_left(sums, sm - upper)
bisect.insort(sums, sm)
return res
``````
Copy The Code &

Input

cmd
nums = [0], lower = 0, upper = 0

Output

cmd
1

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0327_CountOfRangeSum
{
public int CountRangeSum(int[] nums, int lower, int upper)
{
var sums = new long[nums.Length + 1];
for (int i = 0; i  <  nums.Length; i++)
sums[i + 1] = sums[i] + nums[i];

return CountWhileMergeSort(sums, 0, nums.Length + 1, lower, upper);
}

private int CountWhileMergeSort(long[] sums, int start, int end, int lower, int upper)
{
if (end - start  < = 1) return 0;
int mid = start + (end - start) / 2;
int count = CountWhileMergeSort(sums, start, mid, lower, upper)
+ CountWhileMergeSort(sums, mid, end, lower, upper);

int j = mid, k = mid, t = mid;
long[] cache = new long[end - start];
for (int i = start, r = 0; i  <  mid; ++i, ++r)
{
while (k < end && sums[k] - sums[i] < lower) k++;
while (j  <  end && sums[j] - sums[i] <= upper) j++;
count += j - k;

while (t  <  end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
}
for (int i = start; i  <  t; i++)
sums[i] = cache[i - start];

return count;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [0], lower = 0, upper = 0

Output

cmd
1