Fenwick tree

fenwick.py

from typing import List

class FenwickTree(object):
    def __init__(self, n):
        self.t = [1] * (n + 1)
        self.n = n
        self.d = {i: (i & (-i)) for i in range(n)}
        self.build(self.t)
    #
    def build(self, t: List[int]):
        for i in range(1, self.n):
            #p = i + (i & (-i))
            p = i + self.d[i]
            if p <= self.n:
                t[p] += t[i]
    #
    def emptyTillPos(self, i: int) -> int:
        sum: int = 0
        while i:
            sum += self.t[i]
            # i -= (i & (-i))
            i -= self.d[i]
        return sum
    #
    def updatePos(self, i: int, k: int):
        while i < self.n:
            self.t[i] += k
            # i += (i & (-i))
            i += self.d[i]
    #
    def usePos(self, k: int) -> int:
        l, r = 1, self.n
        while l < r:
            mid: int = l + ((r - l) // 2)
            if self.emptyTillPos(mid) <= k:
                l = mid + 1
            else:
                r = mid
        self.updatePos(l, -1)
        return l - 1


from datetime import datetime
tree = FenwickTree(7)

people = []
order = (4, 2, 0, 1, 1, 0)
positions = list(range(6))

s = datetime.now()
for pos in order:
    print(pos, tree.usePos(pos))

e = datetime.now()
print(e - s)

s = datetime.now()
for pos in order:
    print(pos, positions.pop(pos))

e = datetime.now()
print(e - s)