Prefix Sum Technique Explanation.

The Prefix Sum Technique, also known as Prefix Sum Array or Cumulative Sum Array, is a methodology used to efficiently compute and store cumulative sums of elements in an array. It enables fast retrieval of the sum of elements within a specific range of indices in constant time.

Prefix Sum Technique Explanation.

Below are the steps that we need to follow to create a Prefix Sum Array:

Given an array arr of size n, the prefix sum at index i, denoted as prefix[i], represents the sum of elements from index 0 to index i-1 in the original array arr.

The first element of the prefix sum array prefix[0] is initialized as 0 and subsequent elements prefix[i] are computed by adding the current element in the original array arr[i-1] to the previous prefix sum prefix[i-1].

Use this formula to find the sum of elements within a range [left, right] (inclusive) in the original array: sum_range = prefix[right + 1] - prefix[left].

Example:

Let's understand the working with one example,

Original Array:
[3, 1, 7, 4, 2, 0, 5]

Prefix Sum Array:
[0, 3, 4, 11, 15, 17, 17, 22]

Calculation of Prefix Sum Array:
prefix[0] = 0 (initialized)
prefix[1] = prefix[0] + arr[0] = 0 + 3 = 3.
prefix[2] = prefix[1] + arr[1] = 3 + 1 = 4
prefix[3] = prefix[2] + arr[2] = 4 + 7 = 11.
prefix[4] = prefix[3] + arr[3] = 11 + 4 = 14.
prefix[5] = prefix[4] + arr[4] = 14 + 1 = 15.
prefix[6] = prefix[5] + arr[5] = 15 + 2 = 17.
prefix[7] = prefix[6] + arr[6] = 17 + 5 = 22.

To find the sum of elements between indices 2 and 5 (inclusive):

sum_range = prefix[6] - prefix[2] = 17 - 4 = 13

Prefix Sum Code Implementation.

Now I hope that you understand the basic workings of the Prefix Sum Array Technique and why it is so popularly used for solving many coding problems. Let's see the code implementation of this in different programming languages.

C Implementation:

// C Code Implementation of Prefix Sum Array
#include <stdio.h>

void prefixSum(int arr[], int prefix[], int n) {
    prefix[0] = 0; // Initialization

    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
}

int main() {
    int arr[] = {3, 1, 7, 4, 2, 0, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int prefix[n + 1];
    prefixSum(arr, prefix, n);

    printf("Prefix Sum Array: ");
    for (int i = 0; i <= n; i++) {
        printf("%d ", prefix[i]);
    }
    printf("\n");

    return 0;
}

Output:

Prefix Sum Array: 0 3 4 11 15 17 17 22

C++ Implementation:

// C++ Code Implementation of Prefix Sum Array Technique
#include <iostream>
#include <vector>
using namespace std;

void prefixSum(vector<int>& arr, vector<int>& prefix) {
    prefix[0] = 0; // Initialization

    for (int i = 1; i <= arr.size(); i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
}

int main() {
    vector<int> arr = {3, 1, 7, 4, 2, 0, 5};
    int n = arr.size();

    vector<int> prefix(n + 1);
    prefixSum(arr, prefix);

    cout << "Prefix Sum Array: ";
    for (int i = 0; i <= n; i++) {
        cout << prefix[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Prefix Sum Array: 0 3 4 11 15 17 17 22

Java Implementation:

// Java Code Implementation to Print Prefix Sum Array
public class PrefixSum {
    public static void prefixSum(int[] arr, int[] prefix) {
        prefix[0] = 0; // Initialization

        for (int i = 1; i <= arr.length; i++) {
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 7, 4, 8, 0, 5};
        int n = arr.length;

        int[] prefix = new int[n + 1];
        prefixSum(arr, prefix);

        System.out.print("Prefix Sum Array: ");
        for (int i = 0; i <= n; i++) {
            System.out.print(prefix[i] + " ");
        }
        System.out.println();
    }
}

Output:

Prefix Sum Array: 0 3 4 11 15 23 23 28

Python Implementation:

# Python Code Implementation for Prefix Sum Array
def prefix_sum(arr):
    n = len(arr)
    prefix = [0] * (n + 1)

    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + arr[i - 1]

    return prefix

arr = [3, 11, 7, 4, 2, 0, 5]
prefix = prefix_sum(arr)
print("Prefix Sum Array:", prefix)

Output:

Prefix Sum Array: 0 3 14 21 25 27 27 32

Time Complexity: O(n) because we need to traverse the complete array at least once to create the prefix sum array.

Space Complexity: O(n) because we are creating a new prefix sum array of the same size to store the calculated prefix sum of the given array.

Key Points About Prefix Sum Array.

Efficiency: Precomputing prefix sums allow quick retrieval of range sums without recomputation.
Constant Time Complexity: Retrieving a range sum is achieved in constant time O(1) by subtracting prefix sums.
Preprocessing Overhead: Additional space O(n) is required to store the prefix sum array.

The Prefix Sum Technique is commonly used in scenarios where frequent range sum queries need to be answered efficiently, such as in computational geometry, image processing, and various algorithm problems.

Prefix Sum Technique Explanation.