AdvancedMultiple choice
You need prefix sums with point updates on a large array. Fenwick tree or segment tree?
- AFenwick: same bounds with a fraction of the memory and constant factor
- BSegment tree, because Fenwick trees cannot do point updates
- CSegment tree, because it has better asymptotic complexity
- DNeither: use a prefix-sum array and rebuild after each update
The worked solution is in Premium
The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.
Learn the method
Reported in interviews at
More data structures and algorithms questions
- A balanced binary search tree holds one million keys.Foundation
- What is the height (edges on the longest root-to-leaf path) of a binary heap…Foundation
- How many structurally different binary search trees can hold the keys 1,2,3,4,5?Applied
- A root-finding guarantee, part 1 of 3Foundation
- You need the 100 largest values from a stream of 10⁹ numbers you cannot store.Foundation
- How many comparisons does a binary search need, in the worst case, over a…Foundation