ZERO / HERO
Rulers of clever lengths

Fenwick Tree (BIT)

The analogy

You want running totals that survive edits. Each slot secretly stores the total of a block ending at itself, and the block lengths are powers of two chosen so that any prefix is the sum of a few non-overlapping blocks. Walking those blocks is just repeatedly stripping the lowest set bit off a number.

Visualizer

Stripping the lowest bit

step 1 / 8
3
1
4
2
4
3
9
4
5
5
14
6
2
7
31
8

Original array [3, 1, 4, 1, 5, 9, 2, 6]. The Fenwick tree stores, at index i, the sum of the last (i & -i) elements ending at i.tree[i] covers (i & -i) elements

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)        # 1-indexed!

    def add(self, i, delta):
        while i <= self.n:
            self.t[i] += delta
            i += i & -i               # next block up

    def prefix(self, i):
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i               # strip lowest set bit
        return s

    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l - 1)
Check yourself

Why can a plain Fenwick tree not answer range MINIMUM queries?