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

from itertools import accumulate
from bisect import bisect_left

# Define a class for Binary Indexed Tree (Fenwick Tree) data structure.
class BinaryIndexedTree:
    # Initialize the Binary Indexed Tree with `size` elements.
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    # Update the tree by adding a value `val` to the element at index `index`.
    def update(self, index, val):
        # Propagate the update up the tree.
        while index <= self.size:
            self.tree[index] += val
            index += index & -index

    # Query the cumulative sum from index 1 to `index`.
    def query(self, index):
        sum_ = 0
        # Aggregate the sums.
        while index > 0:
            sum_ += self.tree[index]
            index -= index & -index
        return sum_

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # ans = 0
        # for i in range(len(nums)):
        #     for j in range(i , len(nums)+1):
        #         a = sum(nums[i:j])
        #         if  i < j and a >= lower and a <= upper:
        #             ans+= 1
        # return ans
        # Compute the prefix sums of the input array `nums`.
        prefix_sums = list(accumulate(nums, initial=0))
        # Flatten and sort the unique sums for tree construction.
        sorted_arr = sorted(set(x for sum_ in prefix_sums for x in (sum_, sum_ - lower, sum_ - upper)))
        # Initialize the Binary Indexed Tree with the length of the sorted unique sums.
        tree = BinaryIndexedTree(len(sorted_arr))
        count = 0  # Initialize the count of ranges.
      
        # Iterate over the prefix sums.
        for sum_ in prefix_sums:
            # Find the indices for the current sum minus the upper and lower bounds.
            # +1 because our BIT is 1-indexed.
            left = bisect_left(sorted_arr, sum_ - upper) + 1
            right = bisect_left(sorted_arr, sum_ - lower) + 1
            # Calculate the number of sums in the range [lower, upper].
            count += tree.query(right) - tree.query(left - 1)
            # Update the BIT for the current prefix sum.
            tree.update(bisect_left(sorted_arr, sum_) + 1, 1)
      
        # Return the total count of sums in the range.
        return count
45041