Prefix Sum Array in DSA Python - Cheat Sheet & Quick Revision

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. It helps to quickly find the sum of any subarray.

beginner

How do you calculate the prefix sum array for [2, 4, 6, 8]?

Start with the first element: 2. Then add each next element to the sum so far: [2, 2+4=6, 6+6=12, 12+8=20]. So the prefix sum array is [2, 6, 12, 20].

beginner

Why is a prefix sum array useful?

It allows you to find the sum of any part of the array quickly by subtracting two prefix sums instead of adding many elements each time.

intermediate

What is the time complexity to build a prefix sum array of size n?

The time complexity is O(n) because you calculate each prefix sum by adding one element to the previous sum in a single pass.

intermediate

How do you find the sum of elements from index i to j using a prefix sum array?

Sum from i to j = prefix_sum[j] - prefix_sum[i-1] if i > 0, else prefix_sum[j] if i == 0.

What does the element at index 3 in a prefix sum array represent?

A Difference between elements at index 3 and 2

B Value of the original array at index 3

C Sum of elements from index 3 to end of the array

D Sum of elements from index 0 to 3 in the original array

Each prefix sum element at index i is the sum of all original elements from 0 to i.

What is the time complexity to find the sum of any subarray using a prefix sum array?

A O(1)

B O(log n)

C O(n)

D O(n^2)

Using prefix sums, subarray sums can be found in constant time O(1) by subtraction.

If prefix_sum = [3, 7, 12, 18], what is the sum of elements from index 1 to 3?

A 18

B 15

C 12

D 9

Sum = prefix_sum[3] - prefix_sum[0] = 18 - 3 = 15.

Which of the following is NOT true about prefix sum arrays?

A They store the product of elements up to index i

B They require O(n) time to build

C They help in quick range sum queries

D They can be used to optimize sum calculations

Prefix sum arrays store sums, not products.

What is the prefix sum array of [1, 1, 1, 1]?

A [4, 3, 2, 1]

B [1, 1, 1, 1]

C [1, 2, 3, 4]

D [0, 1, 2, 3]

Each element is the sum of all previous elements: 1, 1+1=2, 2+1=3, 3+1=4.

Explain how to build a prefix sum array from a given array and why it is useful.

Think about adding elements one by one and how it helps in fast queries.

Describe how to find the sum of elements between two indices i and j using a prefix sum array.

Use subtraction of prefix sums to get the subarray sum.