Using Binary Tree to solve it.

  • 0

    First we preprocessing the sum array named s[];
    The s[i] represent the sum of the nums[0 -> i] inclusive.

    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++)
    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.

Log in to reply

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