# 327. Count of Range Sum (1)

[Link](https://leetcode.com/problems/count-of-range-sum/)

Given an integer array `nums`, return the number of range sums that lie in `[lower, upper]` inclusive.\
Range sum `S(i, j)` is defined as the sum of the elements in `nums` between indices `i` and `j` (`i` ≤ `j`), inclusive.

**Note:**\
A naive algorithm of O(n^2) is trivial. You MUST do better than that.

**Example:**

```
Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.
```

**Solution**

\
&#x20;For `leetcode 327`, applying the sequential recurrence relation (with `j` fixed) on the pre-sum array, the subproblem `C` reads: **find the number of elements out of visited ones that are within the given range**, which again involves searching on "dynamic searching space"; applying the partition recurrence relation, we have a subproblem `C`: **for each element in the left half, find the number of elements in the right half that are within the given range**, which can be embedded into the merging process using the two-pointer technique.

1. 先將從頭到任何位置的區間sum值放到一個n+1大小的array : sum，其中sum\[i] 表示 nums\[0] + nums\[1] + ... + num\[i-1] 的值，其中num\[i] is exclusive
2. 那麼區間\[i, j-1]的sum值 S(i,j-1)就可以理解成 sum\[j] - sum\[i]，問題就簡化成要求得有多少的S(i, j-1) 符合規則
3. 找尋範圍的方法可透過mergeSort，merge時左右兩邊的已經sort過。針對左邊的每個index i，尋找右邊是否有某個區間(k, j) 使得 S(i, k) \~ S(i, j)都能符合規則，那這時j-k就是針對index i所有可能的區間數

![](https://2628390332-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M0RnkuvOeqe0clAIN1b%2F-M2qXnNDqHjV4i2pV8qT%2F-M2qnPDddC8AYAu8wMrT%2Fimage.png?alt=media\&token=84a6b18a-66bf-4d0d-a299-fc3a94fb516a)

* `j` is the first index satisfy `sums[j] - sums[i] > upper` and
* `k` is the first index satisfy `sums[k] - sums[i] >= lower`.

Then the number of sums in `[lower, upper]` is `j-k`. We also use another index `t` to copy the elements satisfy `sums[t] < sums[i]` to a cache in order to complete the merge sort.

Despite the nested loops, the time complexity of the "merge & count" stage is still linear. Because the indices `k`, `j`, `t` will only increase but not decrease, each of them will only traversal the right half once at most. The total time complexity of this divide and conquer solution is then `O(n log n)`.

One other concern is that the `sums` may overflow integer. So we use long instead.

**Java - Merge Sort Solution**

```
 public int countRangeSum(int[] nums, int lower, int upper) {
        int len = nums.length;
        long[] sum = new long[len + 1];
        
        for(int i = 0; i < len ; i++){
            sum[i+1] = sum[i] + nums[i];
        }
        return mergeSortAndCount(sum, 0, len+1, lower, upper);
    }
    
    
    public int mergeSortAndCount(long[] sum, int start, int end, int lower, int upper){
        if(end - start <= 1) return 0; //remember: merge sort到只剩兩個元素就不用merge了
        int mid = (start + end)/2;
        int count = mergeSortAndCount(sum, start, mid, lower, upper) + mergeSortAndCount(sum, mid, end, lower, upper);
        
        int k = mid, j = mid, t = mid;
        long[] cache = new long[end - start]; //為何是end - start 而非 end -start + 1
        for(int i = start, r = 0; i < mid; i++, r++){ 
            while( k < end && sum[k] - sum[i] < lower) k++;
            while( j < end && sum[j] - sum[i] <= upper) j++;
            //把sort結果存到新的cache array
            while( t < end && sum[t] < sum[i]) cache[r++] = sum[t++];
            cache[r] = sum[i];
            count += j-k;
        }
        System.arraycopy(cache, 0, sum, start, t-start); // 為何是t-start 而非end -start
        return count;
    }
```
