First we preprocessing the sum array named s[];

The s[i] represent the sum of the nums[0 -> i] inclusive.

e.g.

```
nums[] -2 5 -1
s[] -2 3 2
```

For each i and j (j>=i), the answer is how many **pair{i,j}** satisfies the following equation **lower<=s[j]-s[i-1]<=upper** .

And then we transform it into **lower+s[i-1]<=s[j]<=upper+s[i-1]**

With smaller input data, we can use Binary Index Tree. But in this problem, the nums[i] is too large (INT32.max), so we can only use the Balanced Binary Tree to count how many element exist in that range.

Let's see the code.

```
##
# s[0] = nums[0];
# s[1] = nums[0] + nums[1];
# .....
# s[size()-1] = sum(nums[0]...nums[size()-1]);
##
for (int i=0; i<s.size(); i++)
tree.insert(s[i]);
int ans = 0;
for (int i=0; i<nums.size(); i++)
{
if (i>0) //s[-1] is insignificance
tree.remove(s[i-1]); // to satisify j>=i
ans += tree.lessOrEqualCount(upper+s[i-1]) - tree.lessOrEqualCount(lower+s[i-1]-1);
}
return ans;
```

By the way, The *Treap* can solve it with time limit.