<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 TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.count = 1
        self.left = left
        self.right = right
        self.height = 1

class AVLTree:
    def __init__(self):
        self.root = None
    
    def add_value(self, value):
        self.root = self.add(self.root, value)

    def add(self, root, value):
        if not root:
            return TreeNode(value)

        if value == root.val:
            root.count += 1
        elif value < root.val:
            root.left = self.add(root.left, value)
            root.count += 1
        elif value > root.val:
            root.right = self.add(root.right, value)
        root.height = 1 + max(self.height(root.left), self.height(root.right))

        bal = self.balance(root)
        if bal > 1:
            if value > root.left.val:
                root.left = self.left_rotate(root.left)
            root = self.right_rotate(root)
        elif bal < -1:
            if value < root.right.val:
                root.right = self.right_rotate(root.right)
            root = self.left_rotate(root)

        return root

    def height(self, root):
        return root.height if root else 0
        
    def adjust_height(self, root):
		    root.height = 1 + max(self.height(root.left), self.height(root.right))

    def balance(self, root):
        return self.height(root.left) - self.height(root.right) if root else 0

    def left_rotate(self, pivot):
        pivot_next = pivot.right
        pivot_next.left, pivot.right = pivot, pivot_next.left
        pivot_next.count += pivot.count
        self.adjust_height(pivot)
        self.adjust_height(pivot_next)
        return pivot_next

    def right_rotate(self, pivot):
        pivot_next = pivot.left
        pivot_next.right, pivot.left = pivot, pivot_next.right
        pivot.count -= pivot_next.count
        self.adjust_height(pivot)
        self.adjust_height(pivot_next)
        return pivot_next
    
    def find_value(self, val):
        return self.find(self.root, val)
    
    def find(self, root, val):
        if not root:
            return 0
        
        if root.val == val:
            return root.count
        elif root.val <= val:
            return root.count + self.find(root.right, val)
        else:
            return self.find(root.left, val)

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        res = 0
        tree = AVLTree()
        tree.add_value(0)
        total = 0
        for i in range(len(nums)):
            total += nums[i]
            res += tree.find_value(total - lower) - tree.find_value(total - upper - 1)
            tree.add_value(total)
        return res

40038