# 327 Count of Range Sum

## 327. [Count of Range Sum](https://leetcode.com/problems/count-of-range-sum/description/)

## 1. Question

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:**\
Givennums=`[-2, 5, -1]`,lower=`-2`,upper=`2`,\
Return`3`.\
The three ranges are :`[0, 0]`,`[2, 2]`,`[0, 2]`and their respective sums are:`-2, -1, 2`.

## 2. Implementation

**(1) TreeMap**

我们定义sum\[i]为nums\[0...i]之间的subarray sum, 对于区间\[j,i]的subarray sum，其值等于sum\[i] - sum\[j], 如果 lower <= sum\[i] - sum\[j] <= upper, 通过推导可以得出 sum\[j] - upper <= sum\[j] <= sum\[i] - lower. 我们遍历数组的时候，利用sum变量加上当前的数，这样我们很容易得到sum\[i], 要得到sum\[j], 我们利用TreeMap的区间查询的特性，查询treemap，key在 sum\[i] - upper\[i] 和 sum\[i] - lower之间的值的个数，最后得到结果

```java
public class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {        
        TreeMap<Long, Long> map = new TreeMap();
        map.put((long)0, (long)1);
        long sum = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            long fromKey = sum - upper;
            long toKey = sum - lower;
            Map<Long, Long> subMap = map.subMap(fromKey, true, toKey, true);

            for (long value : subMap.values()) {
                count += value;
            }

            if (map.containsKey(sum)) {
                map.put(sum, map.get(sum) + 1);
            }
            else {
                map.put(sum, (long)1);
            }
        }
        return count;
    }
}
```

**(2) Merge Sort**

思路: 这里的思路和Leetcode 315很类似，我们利用merge sort，在merge的过程中count 符合条件的区间和个数. 具体在我们的merge()里，我们知道sum\[start, mid] 和 sum\[mid + 1, end]这两个区间是已经排好序的，对于每个在左区间的数sum\[left], 我们分别要找出一个index high满足sum\[high] - sum\[left] > upper, 以及第一个index low满足sum\[low] - sum\[left] >= lower, 这样符合条件的区间个数就是 high - low. 在计算符合条件的区间个数同时，我们也顺便完成merge的过程

```java
class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        long[] sum = new long[n + 1];

        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        int[] count = new int[1];
        mergeSort(sum, 0, sum.length - 1, lower, upper, count);
        return count[0];
    }

    public void mergeSort(long[] sum, int start, int end, int lower, int upper, int[] count) {
        if (start >= end) {
            return;
        }

        int mid = start + (end - start) / 2;
        mergeSort(sum, start, mid, lower, upper, count);
        mergeSort(sum, mid + 1, end, lower, upper, count);
        merge(sum, start, mid, end, lower, upper, count);
    }

    public void merge(long[] sum, int start, int mid, int end, int lower, int upper, int[] count) {
        long[] temp = new long[end - start + 1];

        int low = mid + 1;
        int high = mid + 1;
        int right = mid + 1;
        int tIndex = 0;

        for (int left = start; left <= mid; left++) {
            while (low <= end && sum[low] - sum[left] < lower) ++low;
            while (high <= end && sum[high] - sum[left] <= upper) ++high;

            count[0] += high - low;

            while (right <= end && sum[right] <= sum[left]) temp[tIndex++] = sum[right++];
            temp[tIndex++] = sum[left];
        }

        while (right <= end) {
            temp[tIndex++] = sum[right++];
        }

        for (int k = start; k <= end; k++) {
            sum[k] = temp[k - start];
        }
    }
}
```

**(3) Segment Tree**

```
```

## 3. Time & Space Complexity

**TreeMap**: 时间复杂度O(nlogn), 空间复杂度O(n)

**Merge Sort**: 时间复杂度O(nlogn), 空间复杂度O(n)