Algorithms and Data Structures · Senior · Question 7 of 75
What problem does a Fenwick tree (binary indexed tree) solve?
- 1Sorting an array in place in O(n) time
- 2Shortest paths in a weighted tree structure
- ✓Correct answer: Prefix sums with updates, both in O(log n)
Explanation
Plain prefix sums make queries O(1) but updates O(n). A Fenwick tree balances both at O(log n) using the lowest set bit of the index (i & -i) to jump between ranges.