Prefix Sum

Prefix Sum is a technique used with arrays to quickly compute the sum of elements in any subarray. It is especially useful when you need to perform multiple range sum queries efficiently.

🔹 Basic Idea

Given an array arr, the prefix sum array prefix is defined as:

\[prefix[i]=arr[0]+arr[1]+⋯+arr[i]\] 
prefix[0] = arr[0]
for i in range(1, len(arr)):
    prefix[i] = prefix[i - 1] + arr[i]

🔹 Use Case: Subarray Sum

Solve this in leetcode

🔗 https://leetcode.com/problems/range-sum-query-immutable/

If you want to calculate the sum of elements from index l to r (arr[l] + arr[l+1] + ... + arr[r]), you can do:

\[sum=prefix[r]−prefix[l−1]\]

(If l == 0, then the sum is just prefix[r].)

🔹 Example 

arr = [2, 4, 1, 3, 5]
# Prefix sum computation
prefix = [2, 6, 7, 10, 15]

To find sum from index 1 to 3 (i.e., 4 + 1 + 3 = 8):

prefix[3]−prefix[0]=10−2=8

🔹 Time Complexity

  • Building prefix sum: \(O(n)\)
  • Query sum from index l to r: \(O(1)\)

Same problem when solved in a naive way i.e find sub array sum of an array between l and r is \(O(n)\) complexity which gets worsened if this method is queried multiple times. With Prefix sum, once prefix array is build, each query is an \(O(1)\) complexit.

📝 Suggested Practice Problems