Binary Indexed Tree (BIT)

class Bit:
    def __init__(self, a):
        self.a = a
        self.n = len(a)
        self.bit = [0] * (self.n + 1)
        for i, x in enumerate(a):
            self.update(i+1, x)

    def update(self, x, val):
        while x <= self.n:
            self.bit[x] += val
            x += x & -x

    def query(self, x):
        sum = 0
        while x > 0:
            sum += self.bit[x]
            x -= x & -x
        return sum