<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 SegmentTree:
    class Node:
        def __init__(self, start, end):
            self.start = start
            self.end = end
            self.left = None
            self.right = None
            self.count = 0

    def __init__(self, start, end):
        def _build(start, end):
            if start > end:
                return None
            if start == end:
                return SegmentTree.Node(start, end)

            mid = (start + end) //2
            node = SegmentTree.Node(start, end)
            node.left = _build(start, mid)
            node.right = _build(mid + 1, end)
            return node
        self.root = _build(start, end)

    def update(self, ind):
        def _update(node):
            if not node or node.start > ind or node.end < ind:
                return
            if node.start == node.end == ind:
                node.count += 1
                return

            _update(node.left)
            _update(node.right)
            node.count = node.left.count + node.right.count

        _update(self.root)

    def query(self, query_start, query_end):
        def _query(node):
            if not node or node.start > query_end or node.end < query_start:
                return 0
            if node.start >= query_start and node.end <= query_end:
                return node.count

            return _query(node.left) + _query(node.right)
        return _query(self.root)

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        presums = [0]
        for num in nums:
            presums.append(presums[-1] + num)

        possible_all_sums = []
        for presum in presums:
            possible_all_sums.append(presum)
            possible_all_sums.append(presum - upper)
            possible_all_sums.append(presum - lower)
        sum_to_ind = {s:ind for ind, s in enumerate(sorted(set(possible_all_sums)))}

        segmentTree = SegmentTree(0, len(sum_to_ind) - 1)

        result = 0
        for presum in presums:
            low = sum_to_ind[presum - upper]
            high = sum_to_ind[presum - lower]
            result += segmentTree.query(low, high)
            segmentTree.update(sum_to_ind[presum])
        return result
75056