🧩 Python DSA Patterns — Prefix Sum ➕🐍

The prefix sum is a simple yet powerful technique for solving range sum and subarray problems.

Instead of recalculating the sum for every new query, you store cumulative sums once and answer queries in O(1).

📝 Building a Prefix Sum Array

We create a prefix array where each index i stores the sum of all elements up to i.

def build_prefix_sum(arr):
    prefix = [0] * len(arr)
    prefix[0] = arr[0]
    for i in range(1, len(arr)):
        prefix[i] = prefix[i-1] + arr[i]
    return prefix

print("Prefix Sum Array:", build_prefix_sum([2, 4, 6, 8]))
# Output: [2, 6, 12, 20]

📝 Range Sum Query in O(1)

Using the prefix array, we can get the sum of any subarray [l..r] in constant time.

def range_sum(prefix, l, r):
    if l == 0:
        return prefix[r]
    return prefix[r] - prefix[l-1]

arr = [2, 4, 6, 8, 10]
prefix = build_prefix_sum(arr)

print("Sum of arr[1..3]:", range_sum(prefix, 1, 3))  # Output: 18
print("Sum of arr[0..4]:", range_sum(prefix, 0, 4))  # Output: 30

✅ Takeaway

• Precompute once, answer fast.
• Prefix sums are perfect for range queries and subarray-based problems.
• Simple idea, but very powerful in reducing complexity.

🏋️ Practice Problems

1. Range Sum Query (basic prefix sum application)
2. Find Equilibrium Index in an array
3. Subarray Sum Equals K

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns