What is Prefix Sum?

The prefix sum of an array is essentially at index 'i' is the sum of all the numbers from the original array from index '0' to 'i'. Basically we tracking the sum of the previous element in the array with the current element in the array, allowing us to answer queries about the subarray in constant time.

function prefixSumArray(arr) {
    const prefixSums = new Array(arr.length);

    prefixSums[0] = arr[0];

    for (let i = 1; i < arr.length; i++) {
        const previousSum = prefixSums[i - 1];
        prefixSums[i] = previousSum + arr[i];
    }
    return prefixSums;
}

The above template is initializing a new array called prefixSums, setting the first element to the passed in array first element as itself since the sum of the first element in the array will just be this. We then iterate through the passed in array starting at the second element index, notice we are adding the previous sum of the prefixSums array to the current element.

Making this a bit clearer, let us say we have the array [2, 4, 5, 7, 8] and we want to store another array where we keep track of the sums individually.

Therefore our new list (rather our prefix sums) will look like the below:

[2, (2+4), (2+4+5), (2+4+5+7), (2+4+5+7+8)]

Which after summing each individual parantheses, our new prefix sum array will look this this below:

[2, 6, 11, 18, 26]

It is much easier and quicker to track these sums instead of having to go through the array every time to add the numbers.

Now you can be able to say what is the prefix sum of all the numbers just by looking at the last index of the prefix sum array, which is 26. Don't believe me? Go ahead and add the original array individually! It is truly fascinating how it all works, hence we can break down the array into this.

With this fast lookup we do have a time complexity of O(n) while we do have to store the prefix sum array in an array the space complexity is O(n).

Range Sum Query - Immutable

Now let's go through an example problem.

Given an integer array nums, calculate the sum of elements between indices left and right (inclusive). You need to answer multiple queries efficiently, you are required to preprocess the array so that each query can be answered in constant time.

Example: Input is nums = [1, 2, 3, 4], a call is made to sumRange(1, 3) and it outputs 9 in constant time.

sumRange(1, 3) should return 9 because the sum of the elements from index 1 to 3 on the array is 2 + 3 + 4 = 9.

function rangeQuery(nums, left, right) {
    const prefixSum = prefixSumHelper(nums);
    // right index minus left is in right order to get sum
    // since the right most element prefix sum is greater than the left
    // it will return a non negative number
    // Example:
    // nums = [1, 2, 3, 4]
    // prefixSum = [0, 1, 3, 6, 10]
    // sumRange(1, 3) = prefixSum[4] - prefixSum[1] = 10 - 1 = 9
    return prefixSum[right + 1] - prefixSum[left];
}

function prefixSumHelper(nums) {
    // store the first index of the prefixSum array as the first element in nums array
    const prefixSumArr = new Array(nums.length).fill(0);
    prefixSumArr[0] = 0;

    // now iterate through the array to get the next element and track the sum
    // set the next index to the previous plus the incoming nums array
    for (let i = 0; i < nums.length; i++) {
        prefixSumArr[i + 1] = prefixSumArr[i] + nums[i];
    }

    return prefixSumArr;
}

In some implementations, as you have seen above, prefix sum arrays are initialized with the first element being a leading 0 to make the formula a bit easier.

With this format the prefixSum[i] is the sum of the first 'i' elements.

Conclusion

This is something I am also still trying to practice daily as of this day as well! Please let me know your thoughts or if you need clarifications down in the comments!