Count of Range Sum

Given an array, a upper bound, a lower bound. find all subarray sum in lower and upper bound.

This question is easily to think of using prefix sum to represent each subarray sum.

sum(i,j) = pSum[j] - pSum[i].

Solution 1: TreeMap

Since each prefix sum may appear mutiple times, we need to keep count of same subarray sum.

pSum[cur] - any <= upper && pSum[cur] - any >= lower.

any >= pSum[cur] - upper.

any <= pSum[cur] - lower

if we could figure out # of satisfied contion any, we add them to our final result.

TreeMap can give us "subMap<from, inclusive, to, inclusive>" "M大写 -?- "

Solution 2 : Augment BST

average : O(n log n) worst case : O(n ^ 2) ->degrade to linkedlist

each node, we have 2 extra attributes :

class TreeNode {
    int val;
    int leftSize;   //# smaller nodes 
    int rightSize;  //# larger nodes
    TreeNode left;
    TreeNode right;
}

it's still same logic, but we use another tree data structure, each time before we are inserting

cur = pSum + array[i].

we search range[cur - upper, cur - lower]. and then we insert cur to BST.

• How to count range ?

  • smaller = countSmaller(cur - upper);
  • upper = countLarger(cur - lower);
  • inSize = total - smaller - upper;

Implementation of insert

public TreeNode insert(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    } else if (root.val == val) {
        root.count++;
    } else if (root.val < val) {
        root.leftCount++;
        root.left = insert(root.left,val);
    } else {
        root.rightCount++;
        root.right = insert(root.right,val);
    }
    return root;
}

Solution 3 : Merge Sort (真是巧妙)

S[j] - S[i] >= lower (j >= i) -> (count smaller after itself)

S[j] - S[i] <= upper (j >= i)

-> (count larger after itself)

During merge phase,

• left half is sorted, right half is sorted.

• iterate through left half with index i. for each i in left half, find two indices j and k.

  • j is first index sums[j] - sums[i] > upper
  • k is first index sums[k] - sums[i] >= lower

  Then number of sums in [lower, upper] is j - k.

• also we need to return sorted array in each phase.

Divide and Conquer Method:

For each index i in left part, how many elements in right is in range [sums[i] + lower, sums[i] + upper]

• keep two ptr to indicate left boundary

• right boundary

Relationship with merge sort :

utilize partly sorted attribute also right half index must be larger than left half index.

int countWhileMergeSort(long[] nums, int start, int end, int lower, int upper) {
    if (end - start <= 1) {
        return 0;
    }
    int mid = start + (end - start) / 2;
    int count = countWhileMergeSort(nums,start,mid,lower,upper) +  countWhileMergeSort(nums,mid,end,lower,upper);
    int j = mid, k = mid, t = mid;
    long[] cache = new long[end - start];
    int r = 0;
    for(int i = start; i < mid; i++) {
        while(k < end && sums[k] < sum[i] + lower) {
            k++;
        }
        while(j < end && sums[j] <= sums[i] + upper) {
            j++;
        }
        while(t < end && sums[t] < sums[i]) {
            cache[r++] = sums[t++];
        }
        cache[r++] = sums[i];
        count += j - k;
    }
    System.arrayCopy(cache,0,sums,start,t - start);
    return count;
}