<p>Given an integer array <code>nums</code> and two integers <code>lower</code> and <code>upper</code>, return <em>the number of range sums that lie in</em> <code>[lower, upper]</code> <em>inclusive</em>.</p>

<p>Range sum <code>S(i, j)</code> is defined as the sum of the elements in <code>nums</code> between indices <code>i</code> and <code>j</code> inclusive, where <code>i &lt;= j</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0], lower = 0, upper = 0
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>-10<sup>5</sup> &lt;= lower &lt;= upper &lt;= 10<sup>5</sup></code></li>
	<li>The answer is <strong>guaranteed</strong> to fit in a <strong>32-bit</strong> integer.</li>
</ul>

class Solution {
    private:
        vector<long long int> merge(vector<long long int>& nums, int start, int mid, int end)
        {
            int i = start;
            int j = mid+1;
            vector<long long int> result;
            while(true)
            {
                if(i==mid+1)
                {
                    while(j<=end)
                    {
                        result.push_back(nums[j]);
                        j++;
                    }
                    break;
                }
                
                else if(j==end+1)
                {
                    while(i<=mid)
                    {
                        result.push_back(nums[i]);
                        i++;
                    }
                    break;
                }
                else
                {
                    if(nums[i]<nums[j])
                    {
                        result.push_back(nums[i]);
                        i++;
                    }
                    else
                    {
                        result.push_back(nums[j]);
                        j++;
                    }
                }
            }
            
            return result;
        }
        
        int mergeSort(vector<long long int>& sums, int start, int end, int lower, int upper)
        {
            if(start>end)
                return 0;
            else if(start==end)
            {
                if(sums[start]>=lower && sums[end]<=upper)
                    return 1;
                else
                    return 0;
            }
            
            int mid = (start+end)/2;
            int result = mergeSort(sums, start, mid, lower, upper)+mergeSort(sums, mid+1, end, lower, upper);
            int i, j, k;
            for(i=start, j=k=mid+1; i<=mid; i++)
            {
                while(j<=end && (sums[j]-sums[i])<lower) ++j;
                while(k<=end && (sums[k]-sums[i]<=upper)) ++k;
                result = result + (k-j);
            }
            
            vector<long long int> temp = merge(sums, start, mid, end);
            for(i=start; i<=end; i++)
                sums[i] = temp[i-start];
                
            return result;
        }
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int n = nums.size(), i;
            if(n==0)
                return 0;
            vector<long long int> sums(n, 0);
            sums[0] = nums[0];
            for(i=1; i<n; i++)
                sums[i] = sums[i-1] + nums[i];
            return mergeSort(sums, 0, n-1, lower, upper);
        }
};
451874