## Table of contents

## 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[0] = nums[0]
prefixSum[1] = prefixSum[0] + nums[1]
prefixSum[2] = prefixSum[1] + nums[2]
...
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[0] = nums[0];
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: