Data Structures24 min read
Fenwick Tree
Learn Fenwick Tree (Binary Indexed Tree) as a simpler structure for prefix sums and updates.
David Miller
December 21, 2025
0.0k0
Fenwick Tree supports: - prefix sum queries - point updates in log time with simple code.
Implementation ```python 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 ```python fw = Fenwick(5) fw.add(1, 5) fw.add(3, 2) print(fw.sum(3)) # 7 ```
Graph: prefix accumulation ```mermaid flowchart LR A[Index] --> B[Jump using lowbit] B --> C[Accumulate] ```
Remember - simpler than segment tree - great for prefix sums
#Python#Advanced#Tree