Binary Indexed Tree

def bit(object):

    def __init__(self, num):
        self.maxIdx = num
        self.tree = [0 for i in range(num)]

    def add(self, idx, val):
        while idx <= self.maxIdx:
            tree[idx] += val
            idx += idx & (~(idx-1))

    def read(self, idx):
        result = 0
        while idx:
            result += tree[idx]
            idx -= idx & (~(idx-1))
        return result

2D bit

def bit_2d(object):

    def __init__(self, num_x, num_y):
        self.max_x = num_x
        self.max_y = num_y
        self.tree = [[0 for i in range(num_y)] for j in range(num_x)]

    def add(self, x, y, val):
        while x <= self.max_x:
            cur_y = y
            while cur_y <= self.max_y:
                tree[x][cur_y] += val
                cur_y += cur_y & (~(cur_y-1))
            x += x & (~(x-1))

    def read(self, x, y):
        result = 0
        while x:
            cur_y = y
            while cur_y:
                result += tree[x][cur_y]
                cur_y -= cur_y & (~(cur_y-1))
            x -= x & (~(x-1))
        return result