this approach is used when we need to calculate a lot of ranges from array, for example:
input = [1,2,3,4,5,6,7]
we need to calculate a sum of ranges ([0, 2], [1, 3], [2,5])
we have 2 methods:
init which is called ones and getSum which will be called for each range

void init(int[] input){
}

int getSum(int from, int to){
}

1. brute force solution

public class Solution{
	private int[] input;
	void init(int[] input){
		this.input = input;
	}

	int getSum(int from, int to){
		var sum = 0;
		for(var i = from; i <= to; i++)
			sum += input[i];
			
		return sum;
	}
}

time complexity:

• init -> O(1)
• getSum -> O(n), where n is the length of input because use n for the worst case and if we have m calls of getSum it's O(m * n)
  momory conplexity O(n)

2. Prefix Sum solution

public class Solution{
	private int[] sums;
	void init(int[] input){
		sums = input;
		for(var i = 1; i < input.Length; i++)
			sums[i] = input[i] + input[i - 1];
	}

	int getSum(int from, int to){
		if(from == 0)
			return sums[to];
			
		return sums[to] - sums[from - 1];
	}
}

• init -> O(n)
• getSum -> O(1) and if we have m calls of getSum it's O(m)
  momory conplexity O(n)

the main idea is calculate sums of all previous elements, like sums[i] = input[i] + input[i - 1]:

input = [1,2,3,4,5,6,7]
sums = [1,3,6,10,15,21,28]