Introduction to Prefix Sum Algorithm

Learn how the Prefix Sum Algorithm simplifies range-sum queries and optimizes computations in arrays.

What is the Prefix Sum Algorithm?

The Prefix Sum Algorithm is a simple yet powerful technique that preprocesses an array to answer range-sum queries efficiently. By creating a prefix sum array, it reduces the time complexity of summing elements between any two indices from O(n) to O(1) after preprocessing.

How It Works

Preprocessing: Build a prefix sum array prefix[i], where each element is the sum of all elements in the original array up to index i.

prefix[i] = prefix[i-1] + arr[i]
Querying: To find the sum of elements between indices l and r, use:

sum = prefix[r] - prefix[l-1]

For l = 0, the sum is directly prefix[r].

Why It's Useful

Efficient Queries: Once the prefix sum array is built, any range sum query takes O(1) time.
Optimized Solutions: Useful for problems involving multiple queries or large arrays, like subarray sums, range updates, or cumulative statistics.

Implementation

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

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

arr = [1, 2, 3, 4, 5]
prefix = build_prefix_sum(arr)
print("Sum from index 1 to 3:", range_sum(prefix, 1, 3))  # Output: 9

Example

Input: arr = [1, 2, 3, 4, 5]
Prefix Array: [1, 3, 6, 10, 15]
Query: Sum of elements from idx 1 to 3 → prefix[3] - prefix[0] = 10 - 1 = 9

Key Takeaway

The Prefix Sum Algorithm is a versatile tool for range-based computations. Its ability to preprocess data for quick queries makes it a go-to strategy for array-related problems in competitive programming and beyond.

Resources

WIP

Introduction