Fenwick Tree for Prefix Sums
Point update, prefix query in log n.
Why Prefix Arrays Break
A plain prefix-sum array answers ranges instantly, but a single update forces you to rebuild it. With many updates, that gets slow. ⏱️
Enter the Fenwick Tree
The Fenwick tree, or BIT, supports both point updates and prefix queries in O(log n). It is your go-to for dynamic running totals.
All lessons in this course
- Fenwick Tree for Prefix Sums
- Inversions with a BIT
- Segment Tree: Build & Query
- Lazy Propagation for Range Updates