Prefix Sum Arrays

Introoduction

In the world of algorithms and data structures, efficiency is everything. When dealing with problems that require frequent range sum queries, recalculating the sum each time can be costly. That’s where the Prefix Sum Array steps in — a simple yet powerful technique that can reduce query time from linear to constant.

What is a Prefix Sum Array

A Prefix Sum Array is an auxiliary array where each element at index i stores the sum of all elements from the start of the array up to index i.

In simple terms, for an array arr, the prefix sum array prefix is defined as:

prefix[i] = arr[0] + arr[1] + ... + arr[i]

This allows us to compute the sum of any subarray in O(1) time after preprocessing.

When and Why to Use it

Use a prefix sum array when:

• You need to calculate the sum of elements in a range multiple times.

• The array is static, i.e., values do not change frequently.

Advantages:

• Preprocessing time: O(n)

• Query time: O(1)

• Great for range sum queries, count queries, and optimization problems.

Step-By-Step Construction

Example:

arr = [3, 6, 2, 8, 1]

We build prefix as follows:

• prefix[0] = arr[0] = 3

• prefix[1] = prefix[0] + arr[1] = 3 + 6 = 9

• prefix[2] = prefix[1] + arr[2] = 9 + 2 = 11

and so on...

So the prefix array becomes:

prefix = [3, 9, 11, 19, 20]

Finding Sum of Any Subarray

Once the prefix sum array is built, you can find the sum of any subarray arr[l..r] using:

sum = prefix[r] - prefix[l - 1] (if l > 0)
sum = prefix[r] (if l == 0)

Example:

Find the sum from index 1 to 3 in arr = [3, 6, 2, 8, 1]:

prefix[r]=prefix[3]=19
prefix[l-1]=prefix[1-1]=prefix[0]=3
=> sum = prefix[3] - prefix[0] = 19 - 3 = 16

Subarray [6, 2, 8] indeed sums to 16.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

vector<int> buildPrefixSum(vector<int>& arr) {
    int n = (int)arr.size();
    vector<int> prefix(n);
    prefix[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    return prefix;
}

int rangeSum(vector<int>& prefix, int l, int r) {
    if (l == 0) return prefix[r];
    return prefix[r] - prefix[l - 1];
}

int main() {
    vector<int> arr = {3, 6, 2, 8, 1};
    vector<int> prefix = buildPrefixSum(arr);

    cout << "Sum from 1 to 3: " << rangeSum(prefix, 1, 3) << "\n";
    return 0;
}

Java Implementation

import java.util.*;

public class PrefixSumArray {
    public static int[] buildPrefixSum(int[] arr) {
        int[] prefix = new int[arr.length];
        prefix[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }
        return prefix;
    }

    public static int rangeSum(int[] prefix, int l, int r) {
        if (l == 0) return prefix[r];
        return prefix[r] - prefix[l - 1];
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 2, 8, 1};
        int[] prefix = buildPrefixSum(arr);

        System.out.println("Sum from 1 to 3: " + rangeSum(prefix, 1, 3));
    }
}

Common Use Cases

1. Range Sum Queries

Used in problems like:

• Find the sum of all elements between indices l and r.

• Count of elements satisfying some condition using 1s and 0s.

2. Subarray Problems

Helpful in:

• Maximum sum subarray problems (e.g., Kadane’s extension)

• Balanced subarrays

• Pattern matching via hashing

3. 2D Prefix Sums

An extension for matrix-based problems where you want to query submatrix sums efficiently.

Tips and Tricks

• Always use long long in C++ or long in Java for large sums to avoid overflow.

• 1-based indexing can sometimes simplify boundary cases.

• Store prefix[0] = 0 to simplify the logic for prefix[r] - prefix[l - 1] when l = 0.

Mistakes to Avoid

• Don’t forget to handle the l = 0 case separately when querying.

• Avoid recalculating prefix sums inside queries. Always preprocess once.

• Use modulo operations carefully if the problem involves large numbers and modulo constraints.

Conclusion

Prefix Sum Arrays are an elegant way to optimize range sum queries and are foundational for mastering competitive programming and data analysis. Once understood, they open the door to more advanced techniques like difference arrays, 2D prefix sums, and sliding window optimizations.

For More Intresting Content ....Click here

Till then,
Happy Coding!!!