leetcode327. Count of Range Sum

Given an integer array 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 O(n2) is trivial. You MUST do better than that.

Example:

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] sums = new long[nums.length+1];
        for(int i = 0 ; i<nums.length ; i++) {
            sums[i+1] = sums[i] + nums[i];
        }
        
        int count = 0;
        for(int i = 0 ; i<nums.length ; i++) {
            for(int j = i+1 ; j<=nums.length ; j++) {
                if(sums[j] - sums[i] >= lower && sums[j] - sums[i] <= upper) {
                    count++;
                }
            }
        }
        return count;
    }

    public int countRangeSum3(int[] nums, int lower, int upper) {
        long[] sums = new long[nums.length + 1];
        for(int i = 0 ; i<nums.length ; i++) {
            sums[i+1] = sums[i] + nums[i];
        }
        long[] sortedSums = new long[nums.length + 1];
        return mergeCountRangeSum3(sums, sortedSums, 0, nums.length+1, lower, upper);
    }
    
    public int mergeCountRangeSum3(long[] sums,long[]  sortedSums, int start, int end, int lower, int upper) {
        if(end - start <= 1) return 0;
        int mid = (start + end) / 2;
        int count = mergeCountRangeSum3(sums, sortedSums, start, mid, lower, upper) 
                + mergeCountRangeSum3(sums, sortedSums, mid, end, lower, upper);
        int firstLargerThanUpper = mid, firstLargerThanLower = mid, indexOfRightHalf = mid;
        for(int i = start, sortedSumsIndex = start; i < mid ; i++, sortedSumsIndex++) {
            while(firstLargerThanUpper < end && sums[firstLargerThanUpper] - sums[i] <= upper)  firstLargerThanUpper++;
            while(firstLargerThanLower < end && sums[firstLargerThanLower] - sums[i] <lower) firstLargerThanLower++;
            while(indexOfRightHalf < end && sums[indexOfRightHalf] < sums[i]) sortedSums[sortedSumsIndex++] = sums[indexOfRightHalf++];
            sortedSums[sortedSumsIndex] = sums[i];
            count += firstLargerThanUpper - firstLargerThanLower;
        }
        System.arraycopy(sortedSums, start, sums, start, indexOfRightHalf - start);
        return count;
    }