Fenwick Tree

Fenwick Tree supports:

• prefix sum queries
• point updates
  in log time with simple code.

Implementation

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)

    def add(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

Usage

fw = Fenwick(5)
fw.add(1, 5)
fw.add(3, 2)
print(fw.sum(3))  # 7

Graph: prefix accumulation

flowchart LR
  A[Index] --> B[Jump using lowbit]
  B --> C[Accumulate]

Remember

• simpler than segment tree
• great for prefix sums