Range Queries: Fenwick & Segment Trees
Advanced · 22 min read · Problem-Solving Patterns, Design, Matrices & Advanced Topics
Prefix sums that survive updates: O(log n) update and query, and counting inversions.
This is an Advanced lesson, part of Premium. What it covers:
- Which structure?
- Fenwick tree (binary indexed tree)
- Fenwick over values: counting smaller elements
- Segment tree
- Practice ladder
- Interview questions
- Further reading