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.

class Solution {
    int lower, upper;

    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] prefixSum = new long[nums.length + 1];
        this.lower = lower;
        this.upper = upper;
        // PrefixSum[i] -> Sum of first i elements
        for (int i = 1; i <= nums.length; i++)
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        return mergeSort(prefixSum, 0, prefixSum.length - 1);
    }

    private int mergeSort(long[] prefixSum, int start, int end) {
        if (start >= end)
            return 0;
        int mid = start + (end - start) / 2;
        // The pairs in the left half and the pairs in the 
        // right half get counted in the recursive calls.
        int leftAns = mergeSort(prefixSum, start, mid);
        int rightAns = mergeSort(prefixSum, mid + 1, end);
        // We just need to also count the pairs that use both halves.
        return leftAns + rightAns + merge(prefixSum, start, end);
    }

    private int merge(long[] prefixSum, int start, int end) {
        int ans = 0, mid = start + (end - start) / 2;
        long[] temp = new long[end - start + 1];
        int pointer1 = start, pointer2 = mid + 1, index = 0;
        int left = mid + 1, right = mid + 1;
        // O(N), because "left" & "right" variables only move right
        while (pointer1 <= mid) {
            // We find a limit, such that we just enter "lower" limit
            while (left <= end && prefixSum[left] - prefixSum[pointer1] < lower)
                left++;
            // We find a limit, such that we just get out of "upper" limit
            while (right <= end && prefixSum[right] - prefixSum[pointer1] <= upper)
                right++;
            // Normal merging process
            while (pointer2 <= end && prefixSum[pointer2] < prefixSum[pointer1])
                temp[index++] = prefixSum[pointer2++];
            temp[index++] = prefixSum[pointer1++];
            // Answer will be [L,R], L is shown by pointer1, & 
            // R is shown by all the values in between [left,right)
            ans += right - left;
        }
        while (pointer2 <= end)
            temp[index++] = prefixSum[pointer2++];
        for (int i = start; i <= end; i++)
            prefixSum[i] = temp[i - start];
        return ans;
    }
}