BIT implementaion with Python

class BinaryIndexedTree(object):
    def __init__(self, n):
        self.n = n # max value
        self.tree = [0] * (n+1)

    def lowbit(self, x):
        return x & ~(x-1)

    def update(self, idx, val):
        while idx <= self.n:
            self.tree[idx] += val
            idx += self.lowbit(idx)

    def read(self, idx):
        sum = 0
        while idx:
            sum += self.tree[idx]
            idx -= self.lowbit(idx)
        return sum