🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← 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?

  1. A.A plain prefix sum array rebuilt after each update
  2. B.A difference array only
  3. C.A Fenwick tree or segment tree
  4. 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 →