Algorithms and Data Structures · Senior · Question 8 of 75
When would you choose a segment tree over a Fenwick tree?
- ✓Correct answer: For range queries like min or max, or for range updates
- 2When the array never changes after creation
- 3When memory must stay strictly below n elements
Explanation
Fenwick trees fit invertible operations like sums. A segment tree stores an aggregate per segment and supports any associative operation (min, max, gcd) and, with lazy propagation, range updates. It uses about 2n to 4n nodes.