# Count of Range Sum

This page explains Java solution to problem `Count of Range Sum`

using `TreeMap`

data structure.

## Problem Statement

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 1:****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

If you have any suggestions in below code, please

create a pull request by clicking here.

```
package com.vc.hard;
import java.util.*;
class CountOfRangeSum {
public int countRangeSum(int[] nums, int lower, int upper) {
TreeMap<Long, Integer> prefixSum = new TreeMap<>();
long sum = 0;
int count = 0;
prefixSum.put(0l, 1);
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
long from = sum - upper;
long to = sum - lower;
Map<Long, Integer> subMap = prefixSum.subMap(from, true, to, true);
for(int value: subMap.values()) count += value;
prefixSum.put(sum, prefixSum.getOrDefault(sum, 0) + 1);
}
return count;
}
}
```

## Time Complexity

O(N * log(N)) Where

N is total number of elements in an input array

## Space Complexity

O(N) Where

N is total number of elements in an input array