Part V · Trees, Priority Structures and Range Queries
29. Fenwick Trees and Segment Trees
7 lessons•39 topics•Intermediate / Advanced
7 of 7 lessons published
29.017 animated
Fenwick tree
- Binary indexed tree
- Lowest set bit
- Point update
- Prefix sum
- Range sum
- Linear build
- O(log n) operations
29.024 animated
Fenwick variants
- Range update/point query
- Range update/range query
- Frequency counting
- Order statistics
- 2D BIT
29.035 animated
Segment tree fundamentals
- Recursive intervals
- Build
- Point update
- Range sum/min/max
- Neutral element
- Query combination
29.046 animated
Lazy propagation
- Range addition
- Range assignment
- Lazy tags
- Push-down
- Tag composition
- Mixed updates
29.056 animated
Advanced segment trees
- Min/max with index
- GCD
- Maximum subarray
- Kth one
- Persistent segment tree
- Dynamic sparse segment tree
29.062 animated
Segment tree extensions
- Merge-sort tree
- Segment tree beats
- 2D segment tree
- Implicit segment tree
29.072 animated
Practical decisions
- Fenwick vs segment tree
- Space costs
- Iterative segment tree
- Index conversions
- Testing range boundaries