<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>

import copy


class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # based on merge sort

        def _merge_sort(res, arr, left, right, lower, upper):
            # exclusive of the right end
            if right - left >= 2:
                mid = left + (right - left) // 2
                res, arr = _merge_sort(res, arr, left, mid, lower, upper)
                res, arr = _merge_sort(res, arr, mid, right, lower, upper)
                res, arr = _merge(res, arr, left, mid, right, lower, upper)
            elif right - left == 1:
                if (arr[left][0] >= lower) and (arr[left][0] <= upper):
                    res[arr[left][1]] += 1
            return res, arr
        
        def _merge(res, arr, left, mid, right, lower, upper):
            # we use two separate points to process merging and counting range sums
            # 
            # NOTE: merge sort ensure that indices for arr's elements from [mid, right)
            # are larger than elements from [left, mid)
            i = left
            j = mid
            k_lower = mid
            k_upper = mid

            sorted_arr = []
            while i < mid:
                lower_bound = arr[i][0] + lower
                upper_bound = arr[i][0] + upper

                # we find how many are in the range of [lower_bound, upper_bound]

                # NOTE: we use "< lower_bound" to include the left end
                while (k_lower < right) and (arr[k_lower][0] < lower_bound):
                    k_lower += 1

                # NOTE: we use "<= upper_bound" to include the right end
                while (k_upper < right) and (arr[k_upper][0] <= upper_bound):
                    k_upper += 1
                
                # print('merge: ', (left, mid, right), 'arr: ', [_[0] for _ in arr[left:right]], 'bound: ', (lower_bound, upper_bound), (k_lower, k_upper))

                res[arr[i][1]] += k_upper - k_lower
                # print(f'{res=}')

                while (j < right) and (arr[i][0] > arr[j][0]):
                    sorted_arr.append(arr[j])
                    j += 1
                
                sorted_arr.append(arr[i])
                i += 1
            
            while j < right:
                sorted_arr.append(arr[j])
                j += 1
            
            for tmp_i in range(len(sorted_arr)):
                arr[left + tmp_i] = sorted_arr[tmp_i]
            
            return res, arr

        arr = copy.deepcopy(nums)
        for tmp_i, tmp_val in enumerate(nums):
            if tmp_i == 0:
                arr[tmp_i] = (arr[0], 0)
            else:
                arr[tmp_i] = (arr[tmp_i] + arr[tmp_i - 1][0], tmp_i)
        
        # result for #range_sums when starting from i
        res = [0 for _ in nums]

        # print('arr before: ', [_[0] for _ in arr])

        res, arr = _merge_sort(res, arr, 0, len(nums), lower, upper)

        # print('arr after: ', [_[0] for _ in arr])
        # print('res: ', res)

        return sum(res)
        
38371