Prefix Sum

Prefix sums are a way to make finding the sum of any subarray fast. A prefix sum array stores the sum of all the elements up to each index in the original array.

Original Array:

nums = [2, 4, 1, 8, 3]

Prefix Sum Array:

prefix = [2, 6, 7, 15, 18]

Here’s how you generate the prefix sum array:

prefix[0] = nums[0] = 2
prefix[1] = nums[0] + nums[1] = 2 + 4 = 6
prefix[2] = nums[0] + nums[1] + nums[2] = 2 + 4 + 1 = 7
prefix[3] = nums[0] + nums[1] + nums[2] + nums[3] = 2 + 4 + 1 + 8 = 15
prefix[4] = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] = 2 + 4 + 1 + 8 + 3 = 18

How to Use Prefix Sums to Find Subarray Sums

Let’s say you want to find the sum of the subarray from index i to j in the original array.

The sum of that subarray is prefix[j] - prefix[i - 1].

Example 1:

Subarray from index i = 1 to j = 3: [4, 1, 8]
Its sum is 4 + 1 + 8 = 13
Using prefix sums: prefix[3] - prefix[0] = 15 - 2 = 13

Example 2:

Subarray from index i = 2 to j = 4: [1, 8, 3]
Its sum is 1 + 8 + 3 = 12
Using prefix sums: prefix[4] - prefix[1] = 18 - 6 = 12

Special Case for i = 0

If i = 0, you would get an out-of-bounds index when you try to access prefix[-1]. To handle this, you can either:

Use 0 as prefix[-1]
Or use the expression prefix[j] - prefix[i] + nums[i]

That’s how prefix sums help you quickly find the sum of any subarray.

The last two columns were blank because they were meant to be placeholders for any specific example you might want to calculate. However, I understand that could be confusing, so let’s fill those in with the example calculations:

Index	Original Array (`nums`)	Prefix Sum Array (`prefix`)	Sum from index `i` to `j`	Calculation Using Prefix Sum
0	2	2	-	-
1	4	6	13 (i=1, j=3)	`prefix[3] - prefix[0] = 15 - 2 = 13`
2	1	7	12 (i=2, j=4)	`prefix[4] - prefix[1] = 18 - 6 = 12`
3	8	15	-	-
4	3	18	-	-

In this revised table, I’ve filled in the last two columns to show how you can use prefix sums to calculate the sum of the subarray from index i to j. I used the examples of summing from i=1 to j=3 and from i=2 to j=4.

The variables i and j represent the starting and ending indices of the subarray in the original array nums that you want to find the sum of. In the examples:

i=1, j=3 means you’re interested in the subarray that starts at index 1 and ends at index 3, which is [4, 1, 8] in the original array nums.
i=2, j=4 means you’re interested in the subarray that starts at index 2 and ends at index 4, which is [1, 8, 3] in the original array nums.

These subarrays include the elements at both the starting index i and the ending index j.

Prefix Sum 1D Array

Description

Given an array of integers, the task is to calculate the Prefix Sum. The Prefix Sum is an array derived from the original array where the value at each position i is the sum of the first i numbers in the original array.

Java

In Java, you can calculate the Prefix Sum by iterating through the array and adding each element to the sum of the previous elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class PrefixSumCalculator {
    public static int[] prefixSum(int[] numbers) {
        int[] prefixSum = new int[numbers.length];
        prefixSum[0] = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + numbers[i];
        }
        return prefixSum;
    }

    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40};
        int[] result = prefixSum(numbers);
        for (int number : result) {
            System.out.print(number + " "); // Output: 10 30 60 100
        }
    }
}

C++

In C++, you can calculate the Prefix Sum in a similar way by iterating through the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>

std::vector<int> prefixSum(std::vector<int>& numbers) {
    std::vector<int> prefixSum(numbers.size());
    prefixSum[0] = numbers[0];
    for (int i = 1; i < numbers.size(); i++) {
        prefixSum[i] = prefixSum[i - 1] + numbers[i];
    }
    return prefixSum;
}

int main() {
    std::vector<int> numbers = {10, 20, 30, 40};
    std::vector<int> result = prefixSum(numbers);
    for (int number : result) {
        std::cout << number << " "; // Output: 10 30 60 100
    }
    return 0;
}

Python

In Python, you can also calculate the Prefix Sum by iterating through the list.

1
2
3
4
5
6
7
8
9
def prefix_sum(numbers):
    prefix_sum = [numbers[0]]
    for i in range(1, len(numbers)):
        prefix_sum.append(prefix_sum[i - 1] + numbers[i])
    return prefix_sum

numbers = [10, 20, 30, 40]
result = prefix_sum(numbers)
print(result) # Output: [10, 30, 60, 100]

These examples cover calculating the Prefix Sum for an array of integers in Java, C++, and Python. They build a new array where each value is the sum of the original array’s values up to that index.

Tabular Representation

Here’s a table that demonstrates the calculation of the prefix sum for the input array [10, 20, 30, 40].

Iteration	Current Element	Prefix Sum So Far	Resulting Prefix Sum Array
0	10	10	[10, -, -, -]
1	20	30	[10, 30, -, -]
2	30	60	[10, 30, 60, -]
3	40	100	[10, 30, 60, 100]

Explanation:

Iteration 0: The first element is 10, so the prefix sum is 10.
Iteration 1: The next element is 20, so the prefix sum is 10 + 20 = 30.
Iteration 2: The next element is 30, so the prefix sum is 10 + 20 + 30 = 60.
Iteration 3: The next element is 40, so the prefix sum is 10 + 20 + 30 + 40 = 100.

The resulting prefix sum array is [10, 30, 60, 100], which represents the sum of all elements in the array up to each corresponding position.

Prefix Sum 2D Array

Description

The concept of Prefix Sum for a 2D array is a powerful and efficient technique often used to perform multiple queries on a grid, such as the sum of elements within a subgrid. It works by precomputing a new 2D array where each cell (i, j) represents the sum of all the elements from the top-left corner (0, 0) to the current cell (i, j). This allows for calculating the sum of any subgrid in constant time after the precomputation step.

Solution

Below are the explanations and code snippets for creating a Prefix Sum array for a given 2D array in Java, C++, and Python.

Java

In Java, you can create the Prefix Sum array by iterating over the original array and adding the values based on the previous rows and columns.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public int[][] prefixSum2D(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    int[][] prefixSum = new int[rows][cols];

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            prefixSum[i][j] = grid[i][j] + (i > 0 ? prefixSum[i-1][j] : 0) + (j > 0 ? prefixSum[i][j-1] : 0) - (i > 0 && j > 0 ? prefixSum[i-1][j-1] : 0);
        }
    }
    return prefixSum;
}

C++

Similarly, in C++, you iterate over the array and accumulate the sums based on the previous rows and columns.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
vector<vector<int>> prefixSum2D(vector<vector<int>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();
    vector<vector<int>> prefixSum(rows, vector<int>(cols));

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            prefixSum[i][j] = grid[i][j] + (i > 0 ? prefixSum[i-1][j] : 0) + (j > 0 ? prefixSum[i][j-1] : 0) - (i > 0 && j > 0 ? prefixSum[i-1][j-1] : 0);
        }
    }
    return prefixSum;
}

Python

In Python, you can achieve the same by following a similar approach using list comprehension.

1
2
3
4
5
6
7
8
def prefixSum2D(grid):
    rows, cols = len(grid), len(grid[0])
    prefixSum = [[0] * cols for _ in range(rows)]

    for i in range(rows):
        for j in range(cols):
            prefixSum[i][j] = grid[i][j] + (prefixSum[i-1][j] if i > 0 else 0) + (prefixSum[i][j-1] if j > 0 else 0) - (prefixSum[i-1][j-1] if i > 0 and j > 0 else 0)
    return prefixSum

The implementation in all three languages involves two nested loops that iterate through the original grid. The value of the prefix sum at any cell (i, j) is calculated based on the values in the original grid and the previously computed cells in the prefix sum grid. This makes the computation efficient and allows for quick querying of subgrid sums later on.

Visual Representation

Let’s take a simple 2D array as an example to illustrate the concept of Prefix Sum for a 2D array.

Original Array (Before)

Suppose we have the following 3x3 grid:

4  2  3
1  5  7
3  6  2

Prefix Sum Array (After)

By applying the prefix sum technique as described earlier, we will compute the following 3x3 grid:

4   6   9
5  12  22
8  21  34

Explanation

Here’s how we computed the Prefix Sum Array:

First cell (0, 0) remains the same as in the original array: 4.
Second cell (0, 1) is the sum of original cells (0, 0) and (0, 1): 4 + 2 = 6.
Third cell (0, 2) is the sum of original cells (0, 0), (0, 1), and (0, 2): 4 + 2 + 3 = 9.
Fourth cell (1, 0) is the sum of original cells (0, 0), (1, 0): 4 + 1 = 5.
Fifth cell (1, 1) is the sum of original cells (0, 0), (0, 1), (1, 0), and (1, 1): 4 + 2 + 1 + 5 = 12.
And so on, until the entire prefix sum array is computed.

The prefix sum array allows us to quickly determine the sum of any subgrid within the original array. For example, the sum of the values in the subgrid from (1, 1) to (2, 2) in the original array is 5 + 7 + 6 + 2 = 20, which can be computed in constant time using the prefix sum array.

Prefix Sum for Binary Tree

Prefix Sum for a binary tree allows us to precompute sums for various sections of the tree so that we can answer sum queries (e.g., sum of values along a particular path or within a certain subtree) more efficiently.

The Prefix Sum is computed by performing a Depth-First Traversal (DFS) of the tree, where for each node, we add its value to the sum of its parent’s prefix sum. This process continues recursively for all nodes, and the final result gives us the sum from the root to every node in the tree.

The Prefix Sum for a binary tree can be very helpful in scenarios where we want to query sums of values along certain paths or within specific subtrees multiple times.

Solution

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public void prefixSum(TreeNode root, int currentSum) {
    if (root == null) return;

    // Add current node's value to the prefix sum
    currentSum += root.val;

    // Store the current prefix sum for further use or queries
    root.val = currentSum;

    // Compute prefix sums for left and right children
    prefixSum(root.left, currentSum);
    prefixSum(root.right, currentSum);
}

C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void prefixSum(TreeNode* root, int currentSum) {
    if (root == nullptr) return;

    // Add current node's value to the prefix sum
    currentSum += root->val;

    // Store the current prefix sum for further use or queries
    root->val = currentSum;

    // Compute prefix sums for left and right children
    prefixSum(root->left, currentSum);
    prefixSum(root->right, currentSum);
}

Python Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def prefixSum(root, currentSum):
    if root is None:
        return

    # Add current node's value to the prefix sum
    currentSum += root.val

    # Store the current prefix sum for further use or queries
    root.val = currentSum

    # Compute prefix sums for left and right children
    prefixSum(root.left, currentSum)
    prefixSum(root.right, currentSum)

These code snippets traverse the binary tree and calculate the prefix sum for each node. The prefix sum at any given node represents the sum of all the values from the root node to that particular node in the tree. This information can later be used to answer various types of sum-related queries efficiently.

Prefix sum is a powerful technique that can be used to preprocess an array to facilitate fast queries on sum of elements in particular subarrays, without modifying the original array. With the help of prefix sums, we can compute sums over subarrays in constant time.

How to Compute Prefix Sum:

Create a new array prefixSum of the same size as the original array. prefixSum[0] = originalArray[0] For every index i from 1 to n-1, prefixSum[i] = prefixSum[i-1] + originalArray[i]

C++ Implementation:

1
2
3
4
5
6
7
8
9
vector<int> computePrefixSum(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefixSum(n, 0);
    prefixSum[0] = nums[0];
    for(int i=1; i < n; i++) {
        prefixSum[i] = prefixSum[i-1] + nums[i];
    }
    return prefixSum;
}

Benefits of Prefix Sum:

Quickly find the sum of any subarray using just two array lookups. Helps in reducing the time complexity of summing over subarrays from O(n) to O(1).