Fenwick Tree from unittest import TestCase class Fenwick: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def add(self, i, delta): while i <= self.n: self.tree[i] += delta i += i & -i def sum(self, i): res = 0 while i > 0: res += self.tree[i] i -= i & -i return res def sum_range(self, i, j): return self.sum(j) - self.sum(i - 1) class TestFenwick(TestCase): def test_fenwick(self): tree = Fenwick(10) tree.add(1, 1) tree.add(2, 2) tree.add(3, 3) self.assertEqual(tree.sum(1), 1) self.assertEqual(tree.sum(2), 3) self.assertEqual(tree.sum(3), 6) self.assertEqual(tree.sum(2, 3), 5) tree.add(1, 100) self.assertEqual(tree.sum(3), 106)