## Given problem

Supposed we have an array like that:

``````int[] nums = {3, 4, 2, 6, 8, 9}
``````

We need to calculate the sum of the subarray from:

• 0 –> 2
• 2 –> 4
• 1 –> 3

## Using brute force algorithm

The normal way to deal with it is that we will iterate all elements from i index to j index. Then, we will calculate the sum of this subarray.

Below is the source code of this algorithm.

``````public static int bruteForceSumSubarray(int[] nums, int start, int end) {
if (nums == null) {
return 0;
}

int sum = 0;
for (int i = start; i <= end; ++i) {
sum += nums[i];
}

return sum;
}
``````

When we have m queries, the time complexity of this algorithm:

• Time complexity: O(n * m), n is the size of array
• Space complexity: O(1)

## Using prefix sum algorithm

The idea of prefix sum technique is that it describes a way to pre-compute the cummulative sum for each value in a sequence. So they can be used later for a faster calculation of the total between the given indexes.

Supposed we have an array like that:

``````int[] nums = {3, 4, 2, 6, 8, 9}
``````

Our problem is that we need to calculate a new array `prefixSum` that satisfies some properties:

``````prefixSum = nums
prefixSum = prefixSum + nums
prefixSum = prefixSum + nums

...

prefixSum[i] = prefixSum[i - 1] + nums[i]
``````

Below is the source code of prefix sum algorithm.

``````public static void main(String[] args) {
int[] nums = {3, 4, 2, 6, 8, 9};
int[] prefixSum = new int[nums.length];

calculatePrefixSum(nums, prefixSum);
IntStream.of(prefixSum).forEach(item -> System.out.print(item + " --> "));
System.out.println(" null ");
}

public static void calculatePrefixSum(int[] nums, int[] prefixSum) {
if (nums == null || prefixSum == null) {
return;
}

int length = nums.length;
if (length == 0) {
return;
}

prefixSum = nums;
for (int i = 1; i < length; ++i) {
prefixSum[i] = prefixSum[i - 1] + nums[i];
}
}

public static int sumSubarrayWithPrefixSum(int[] prefixSum, int start, int end) {
int previousSum = start == 0 ? 0 : prefixSum[start - 1];
return prefixSum[end] - previousSum;
}
``````

The complexity of this algorithm:

• Time complexity: O(n + m)
• Space complexity: O(n)

## When to use

• When we have multiple queries for our array.

## Wrapping up

• This prefix sum algorithm applied in Counting sort.

Refer:

https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf

https://codility.com/media/train/3-PrefixSums.pdf