← Quiz: Prefix Sums and Difference Arrays: all 13 questions
Quiz: Prefix Sums and Difference Arrays · Question 8 of 13
Updates and range-sum queries come mixed together, 10⁵ of each. What do you need?
Updates and range-sum queries come mixed together, 10⁵ of each. What do you need?
- A.A plain prefix sum array rebuilt after each update
- B.A difference array only
- C.A Fenwick tree or segment tree
- D.Sorting the array first
Answer & explanation
Correct answer: A Fenwick tree or segment tree
A prefix sum array costs O(n) to rebuild after every update; a Fenwick or segment tree handles both in O(log n).
Can you get the rest right without peeking?
Take the timed Quiz: Prefix Sums and Difference Arrays quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →