# Using Binary Tree to solve it.

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.