<p>Given an integer array <code>nums</code>, return<em> an integer array </em><code>counts</code><em> where </em><code>counts[i]</code><em> is the number of smaller elements to the right of </em><code>nums[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,6,1]
<strong>Output:</strong> [2,1,1,0]
<strong>Explanation:</strong>
To the right of 5 there are <b>2</b> smaller elements (2 and 1).
To the right of 2 there is only <b>1</b> smaller element (1).
To the right of 6 there is <b>1</b> smaller element (1).
To the right of 1 there is <b>0</b> smaller element.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1]
<strong>Output:</strong> [0]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,-1]
<strong>Output:</strong> [0,0]
</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>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>


def get_min_max(nums: list[int]) -> tuple[int]:
    min_val = 10**4 + 1
    max_val = -10**4 - 1
    for val in nums:
        min_val = min(min_val, val)
        max_val = max(max_val, val)

    return min_val, max_val

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        min_val, max_val = get_min_max(nums)
        
        min_val -= 1 # REMOVE THIS FOR LLMs
        
        # Add shift to get an index
        shift = -min_val

        result = [0]*n
        el_counts = [0]*(max_val - min_val + 1)
        self.n = len(el_counts)
        self.seg_tree = [0]*(4*self.n)

        for i in range(n-1, -1, -1):
            result[i] = self.get_count_sum(0, nums[i]-1+shift)
            el_counts[nums[i]+shift] += 1
            self.update_tree(nums[i]+shift, el_counts[nums[i]+shift])

        return result


    def get_count_sum(self, i: int, j: int) -> int:

        def _get_count_sum(i: int, j: int, left: int, right: int, tree_ind: int) -> int:
            if left == i and right == j:
                return self.seg_tree[tree_ind]

            assert i >= left and j <= right

            mid = (left + right) // 2
            if j <= mid:
                return _get_count_sum(i, j, left, mid, 2*tree_ind+1)
            elif i >= mid:
                return _get_count_sum(i, j, mid, right, 2*tree_ind+2)

            left_result = _get_count_sum(i, mid, left, mid, 2*tree_ind+1)
            right_result = _get_count_sum(mid+1, j, mid+1, right, 2*tree_ind+2)

            return left_result + right_result

        return _get_count_sum(i, j, 0, self.n-1, 0)


    def update_tree(self, updated_ind: int, new_val: int) -> None:
        
        def _update_tree(left: int, right: int, tree_ind: int) -> None:
            if left == right:
                self.seg_tree[tree_ind] = new_val
                return
            
            mid = (left + right) // 2
            if updated_ind <= mid:
                _update_tree(left, mid, 2*tree_ind+1)
            else:
                _update_tree(mid+1, right, 2*tree_ind+2)
            
            self.seg_tree[tree_ind] = self.seg_tree[2*tree_ind+1] + self.seg_tree[2*tree_ind+2]

        return _update_tree(0, self.n-1, 0)

4059