[Template]Binary Indexed Tree

class BinaryIndexedTree:
    def __init__(self, arr):
        self.size = len(arr)
        self.tree = [0 for _ in range(self.size + 1)]
        self.build(arr)

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

    def build(self, arr):
        pre = [0 for _ in range(self.size + 1)]
        for index in range(1, self.size + 1):
            pre[index] = pre[index - 1] + arr[index - 1]
            self.tree[index] = pre[index] - pre[index - self.lowbit(index)]

    def add(self, index, value):
        while index <= self.size:
            self.tree[index] += value
            index += self.lowbit(index)

    def query(self, left, right):
        print(self.presum(right) - self.presum(left - 1))

    def presum(self, index):
        res = 0
        while (index > 0):
            res += self.tree[index]
            index -= self.lowbit(index)
        return res
Add New Comment