<reponame>anCoderr/leetcodeSolutions
from math import *
from typing import List, Optional
from collections import Counter
import random
from heapq import *

from LeetcodeSolutionsPython.binary_indexed_tree import BinaryIndexedTree
from tree_node import *


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        offset = 10000
        buckets = [0] * (2 * offset + 2)
        ans = []
        for i in nums:
            buckets[offset + i] += 1
        BIT = BinaryIndexedTree()
        bit_tree = BIT.build_tree(buckets)
        for i in nums:
            ans.append(BIT.get_sum(bit_tree, offset + i - 1))
            BIT.update_tree(bit_tree, i + offset + 1, -buckets[i])
        return ans


solution = Solution()
print(solution.countSmaller([5, 2, 6, 1, 0]))

from math import *
from typing import List, Optional
from collections import Counter
import random
from heapq import *

from LeetcodeSolutionsPython.binary_indexed_tree import BinaryIndexedTree
from tree_node import *


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        offset = 10000
        buckets = [0] * (2 * offset + 2)
        ans = []
        for i in nums:
            buckets[offset + i] += 1
        BIT = BinaryIndexedTree()
        bit_tree = BIT.build_tree(buckets)
        for i in nums:
            ans.append(BIT.get_sum(bit_tree, offset + i - 1))
            BIT.update_tree(bit_tree, i + offset + 1, -buckets[i])
        return ans


solution = Solution()
print(solution.countSmaller([5, 2, 6, 1, 0]))