Recall & Review
beginner
What is a Prefix Sum Array?
A Prefix Sum Array is a new array where each element at index i is the sum of all elements from the start up to i in the original array.
Click to reveal answer
beginner
How do you compute the prefix sum array for an input array?
Start with the first element same as original. For each next element, add the current original element to the previous prefix sum element.
Click to reveal answer
intermediate
Why use a Prefix Sum Array?
It helps quickly find the sum of any subarray by subtracting two prefix sums, reducing repeated addition.
Click to reveal answer
beginner
What is the time complexity to build a prefix sum array of size n?
O(n), because you calculate each prefix sum element once by adding the previous prefix sum and current element.
Click to reveal answer
intermediate
How to find the sum of elements between indices i and j using prefix sums?
Sum = prefixSum[j] - prefixSum[i-1] (if i > 0), else prefixSum[j] if i == 0.
Click to reveal answer
What does the element at index 3 in a prefix sum array represent?
✗ Incorrect
Each prefix sum element at index i is the sum from start (0) to i.
What is the time complexity to answer sum queries using prefix sums after building it?
✗ Incorrect
Sum queries can be answered in constant time by subtracting two prefix sums.
If prefixSum[4] = 15 and prefixSum[1] = 5, what is the sum of elements from index 2 to 4?
✗ Incorrect
Sum = prefixSum[4] - prefixSum[1] = 15 - 5 = 10.
Which of these is NOT a benefit of prefix sum arrays?
✗ Incorrect
Prefix sum arrays use extra memory equal to original array size.
What is the prefix sum of the array [2, 4, 6]?
✗ Incorrect
Prefix sums: 2, 2+4=6, 6+6=12.
Explain how to build a prefix sum array from a given array.
Think of adding one element at a time to the sum of all before it.
You got /3 concepts.
Describe how prefix sum arrays help in finding the sum of any subarray quickly.
Subtract sums to get subarray sum.
You got /3 concepts.