Segment Tree & BIT Practice Questions
Eight problems spanning the whole toolkit: point-update segment trees, range-minimum, lazy propagation, value-indexed BITs with coordinate compression, 2D, and interval-overlap. Once you’ve done these, “range query on a changing array” is a solved problem for you.
The recognition checklist:
- Repeated range queries on a mutable array → segment tree or BIT.
- Only prefix/range sums → BIT (shorter); min/max/gcd → segment tree.
- Range updates (add to a whole range) → lazy propagation.
- “How many smaller / in range” counting → value-indexed BIT + coordinate compression.
- Overlapping intervals / “max overlap” → segment tree on compressed coordinates (or a sweep line).
Medium
| Problem | Pattern | Status |
|---|---|---|
| Range Sum Query — Mutable | the canonical point-update sum tree / BIT | Available |
| Range Minimum Query | segment tree with min aggregate | Available |
| Range Addition | difference array / range-update lazy | Available |
Hard
| Problem | Pattern | Status |
|---|---|---|
| Count of Smaller Numbers After Self | value-indexed BIT, right-to-left | Available |
| Reverse Pairs | BIT / segment tree with compression | Available |
| Range Sum Query 2D — Mutable | 2D Fenwick tree | Available |
| My Calendar III | max-overlap, sweep / lazy segment tree | Available |
| Falling Squares | lazy range-assign + coordinate compression | Available |
More Practice (Coming Soon)
| Problem | Pattern | Status |
|---|---|---|
| Count of Range Sum | BIT on prefix sums | Coming Soon |
| The Skyline Problem | segment tree / sweep | Coming Soon |
| Number of Longest Increasing Subsequence | segment tree on values | Coming Soon |
| Range Module | interval segment tree | Coming Soon |
| Rectangle Area II | sweep line + segment tree | Coming Soon |
| Queue Reconstruction by Height | order-statistic BIT | Coming Soon |
| Maximum Sum of 3 Non-Overlapping Subarrays | prefix + segment tree | Coming Soon |
| Shifting Letters / Range XOR | BIT of XOR | Coming Soon |