← Back to the trees page
Segment Tree & Fenwick Tree (BIT)
Range-query machines: answer "sum/min/max over [l, r]" and update single points, both in O(log n).
What to know
- Segment tree: each node covers an interval; queries stitch O(log n) disjoint nodes.
- Fenwick tree does prefix sums in ~10 lines using low-bit index jumps.
- Lazy propagation extends segment trees to range updates.
- Choose Fenwick for sums; segment tree for min/max/custom merges.
In the wild: Leaderboard rank queries, time-series rollups, computational geometry sweeps.
Algorithms to reach for
Segment tree query/update
O(log n)Range aggregates with point updates
Lazy propagation
O(log n)Range updates deferred until needed
Fenwick prefix sums
O(log n)Count smaller after self, inversions
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.