← Quiz: Segment Tree and Fenwick Tree: all 10 questions
Quiz: Segment Tree and Fenwick Tree · Question 1 of 10
Why are plain prefix sums a poor choice when values change often?
Why are plain prefix sums a poor choice when values change often?
- A.They give wrong answers for negative numbers
- B.Changing one value changes every prefix sum after it, so each update costs O(n)
- C.They use too much memory
- D.They cannot answer range queries
Answer & explanation
Correct answer: Changing one value changes every prefix sum after it, so each update costs O(n)
Queries stay O(1), but frequent updates make the total work O(n) per update.
Can you get the rest right without peeking?
Take the timed Quiz: Segment Tree and Fenwick Tree quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →