Create Sorted Array through Instructions LeetCode solution in Python

1
class Fenwick:
2
    """Fenwick tree aka binary indexed tree"""
3

4
    def __init__(self, n):
5
        self.nums = [0] * (n + 1)
6

7
    def sum(self, k):
8
        ans = 0
9
        while k:
10
            ans += self.nums[k]
11
            k &= k - 1
12
        return ans
13

14
    def add(self, i, x):
15
        i += 1
16
        while i < len(self.nums):
17
            self.nums[i] += x
18
            i += i & -i
19

20

21
class Solution:
22
    def createSortedArray(self, instructions: List[int]) -> int:
23
        ans = 0
24
        fen = Fenwick(10**5)
25
        freq = {}  # frequency of each instructions
26
        for i, x in enumerate(instructions):
27
            less = fen.sum(x)
28
            more = i - freq.get(x, 0) - less
29
            ans += min(less, more)
30
            fen.add(x, 1)
31
            freq[x] = 1 + freq.get(x, 0)
32
        return ans % 1_000_000_007