Stage 1 · Code
Advanced Data Structures
Fenwick Tree
Binary Indexed Tree for prefix sums and range queries.
6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Fenwick Tree Concept
Fenwick Tree (Binary Indexed Tree) stores prefix sums in an array of size n+1. tree[i] = sum of elements from i - (i & -i) + 1 to i. Supports point updates and prefix queries in O(log n). More space-efficient than segment tree.
Gofenwick-tree-implementation.go
38 linesLn 1, Col 1Go
1-indexed. Update: add delta to all responsible ranges (i += i & -i). Query: sum responsible ranges (i -= i & -i). Build: O(n) by propagating values forward.
Core Operations
| Operation | Time | Description |
|---|---|---|
| Point update | O(log n) | Add delta at index |
| Prefix sum | O(log n) | Sum of [1..i] |
| Range sum | O(log n) | Query(r) - Query(l-1) |
| Build | O(n) | From array |
| Find k-th | O(log n) | Binary search on prefix sums |
Range Queries
Gorange-sum-and-point-update.go
10 linesLn 1, Col 1Go
Range sum = prefix(r) - prefix(l-1). Point set: compute current value, update delta.
Variants
- Fenwick for min/max: Use min/max instead of sum (no range query, only prefix).
- 2D Fenwick: tree[x][y] for 2D range sum. O(log² n).
- Range update, point query: Use two BITs or difference array technique.
- Range update, range query: Two BITs or segment tree with lazy.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.