Fenwick Tree

fenwick_tree.py

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, value):
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

    def range_sum(self, start, end):
        return self._prefix_sum(end) - self._prefix_sum(start - 1)

    def _prefix_sum(self, index):
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

f = FenwickTree(10)
f.update(1, 1)
f.update(2, 2)
f.update(3, 3)
f.update(4, 4)
f.update(5, 5)
f.update(6, 6)
f.update(7, 7)
f.update(8, 8)
f.update(9, 9)
f.update(10, 10)
print(f.range_sum(1, 10)) # 55
print(f.range_sum(1, 5)) # 15
print(f.range_sum(6, 10)) # 40
print(f.range_sum(3, 7)) # 25
print(f.range_sum(2, 8)) # 35
print(f.range_sum(4, 9)) # 39
print(f.range_sum(5, 5)) # 5
print(f.range_sum(1, 1)) # 1
print(f.range_sum(10, 10)) # 10

# The indices in Fenwick Tree are 1-based, 
# so be careful with off-by-one errors.