Given an integer array

Range sum

`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

A naive algorithm of

*O*(*n*2) is trivial. You MUST do better than that.
Example:

Given

Return

The three ranges are :

Given

*nums*=`[-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`

.**Solution 1: Use Segment Tree**

**Solution 2: Use Binary Search Tree**

## No comments:

## Post a Comment