fenwick tree

class FenwickTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.BITTree = [0] * (self.n + 1)

        for i in range(self.n):
            self.update(i, arr[i])

    def get_sum(self, i):
        s = 0
        i = i + 1

        while i > 0:
            s += self.BITTree[i]
            i -= i & (-i)

        return s

    def update(self, i, v):
        i += 1

        while i <= self.n:
            self.BITTree[i] += v
            i += i & (-i)


# Driver code to test the FenwickTree class
freq = [2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9]
fenwick_tree = FenwickTree(freq)

print("Sum of elements in arr[0..5] is " + str(fenwick_tree.get_sum(5)))

freq[3] += 6
fenwick_tree.update(3, 6)
print("Sum of elements in arr[0..5] after update is " + str(fenwick_tree.get_sum(5)))