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

# lower <= presum[j]-presum[i-1] <= upper
# lower + presum[i-1] <= presum[j] <= upper + presum[i-1]

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        n = len(nums)
        track = set()
        presum = nums.copy()
        for i in range(1, n):
            presum[i] += presum[i-1]

        for ele in nums:
            track.add(ele)

        track.add(lower)
        track.add(upper)
        for ele in presum:
            track.add(ele)
            track.add(ele+lower)
            track.add(ele+upper)
        
        track = list(track)
        track.sort()
        m = {}
        for i, num in enumerate(track):
            m[num] = i+1

        N = len(track)
        bit = [0]*(N+1)

        def update(x, val):
            while x <= N:
                bit[x] += val
                x += (x&-x)
        
        def query(x):
            res = 0
            while x > 0:
                res += bit[x]
                x -= (x&-x)
            return res

        # print(m)
        ans = 0
        for i in range(n-1, -1, -1):
            update(m[presum[i]], 1)
            prev = 0
            if i > 0:
                prev = presum[i-1]
            # print(i, bit, m[prev+upper], m[prev+lower]-1)
            r = query(m[prev+upper])
            l = query(m[prev+lower]-1)
            if r > 0:
                ans += (r-l)
        return ans
58381