Binary index tree (Fenwick tree) implemented in Python as a wrapper for lists

binary_index_tree.py

class BinaryIndexTree(list):

    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self._tree = list()
        self._rebuild_tree()

    @staticmethod
    def _lowest_one_bit(i):
        return i & -i

    def _rebuild_tree(self):
        # copy
        self._tree = [None] + [item for item in self]
        # rebuild
        for index in range(1, len(self._tree)):
            parent_index = index + self._lowest_one_bit(index)
            if parent_index < len(self._tree):
                self._tree[parent_index] += self._tree[index]

    def __setitem__(self, index, value):
        # get existing value and update array
        existing_val = self[index]
        super().__setitem__(index, value)
        # calculate change
        delta = value - existing_val
        # update tree
        index = (index % len(self) + 1)  # tree is 1 based
        while index < len(self) + 1:  # tree is 1 based
            self._tree[index] += delta
            index += self._lowest_one_bit(index)

    def _sum_up_to_index(self, index):
        s = 0
        index += 1  # tree is 1 based
        while index > 0:
            s += self._tree[index]
            index -= self._lowest_one_bit(index)
        return s

    def range_sum(self, i: int, j: int) -> object:
        i = i % len(self)
        j = j % len(self)
        return self._sum_up_to_index(j) - self._sum_up_to_index(i-1)

    def append(self, object) -> None:
        super().append(object)
        self._rebuild_tree()

    def extend(self, iterable) -> None:
        super().extend(iterable)
        self._rebuild_tree()