<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:
    def __init__(self, n: int) -> None:
        self.n = n
        self.tree = [0]*(4*n)
        self.tags = [0]*(4*n)
    
    def _pushdown(self, idx: int, s: int, mid: int, e: int) -> None:
        if self.tags[idx] != 0:
            self.tags[idx*2] += self.tags[idx]
            self.tags[idx*2+1] += self.tags[idx]
            self.tree[idx*2] += (mid-s+1)*self.tags[idx]
            self.tree[idx*2+1] += (e-mid)*self.tags[idx]
            self.tags[idx] = 0
            
    def update(self, t_s: int, t_e: int, s: int, e: int, idx: int, val: int) -> None:
        if t_s <= s and t_e >= e:
            self.tree[idx] += val*(e-s+1)
            self.tags[idx] += val
        elif t_e < s or t_s > e:
            return
        else:
            mid = (s+e)//2
            self._pushdown(idx, s, mid, e)
            self.update(t_s, t_e, s, mid, 2*idx, val)
            self.update(t_s, t_e, mid+1, e, 2*idx+1, val)
            self.tree[idx] = self.tree[2*idx] + self.tree[2*idx+1]
    
    def query(self, t_s: int, t_e: int, s: int, e: int, idx: int) -> int:
        if t_s <= s and t_e >= e:
            return self.tree[idx]
        elif t_e < s or t_s > e:
            return 0
        else:
            mid = (s+e)//2
            self._pushdown(idx, s, mid, e)
            left = self.query(t_s, t_e, s, mid, 2*idx)
            right = self.query(t_s, t_e, mid+1, e, 2*idx+1)
            return left+right

class Solution:
    def preprocess(self, prefix: List[int], lower: int, upper: int) -> Dict[int, int]:
        points = set()
        for p in prefix:
            points.add(p)
            points.add(p-lower)
            points.add(p-upper)
        points = sorted(list(points))
        map_prefix = {}
        for idx, p in enumerate(points):
            map_prefix[p] = idx
        return map_prefix
    
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        prefix = [0]*len(nums)
        n = len(nums)*3+3
        sg_tree = SegmentTree(n)
        for i in range(len(nums)):
            if i==0:
                prefix[i] = nums[i]
            else:
                prefix[i] = nums[i]+prefix[i-1]
        map_prefix = self.preprocess(prefix, lower, upper)
        ans = 0
        for i in range(len(nums)):
            p = prefix[i]
            if lower <= p <= upper:
                ans += 1
            p_idx = map_prefix[p]
            lo, hi = map_prefix[p-upper], map_prefix[p-lower]
            res = sg_tree.query(lo, hi, 0, n-1, 1)
            ans += res
            sg_tree.update(p_idx, p_idx, 0, n-1, 1, 1)
        
        return ans
        
        
70053