Imagine being asked multiple times:

“What’s the sum from index L to R?”

If you loop every time, your solution becomes slow.

But what if you could answer every query in O(1)?

That’s exactly what Prefix Sum does.

What is Prefix Sum?

Prefix sum stores cumulative sums.

Each index stores sum from 0 to i

int[] arr = {3, 1, 4, 2};

int[] prefix = new int[arr.length];

prefix[0] = arr[0];

for (int i = 1; i < arr.length; i++) {

prefix[i] = prefix[i-1] + arr[i];

}

Result:

prefix = [3, 4, 8, 10]

Why Prefix Sum is Powerful

Without prefix sum:

Each query → O(n)

With prefix sum:

Preprocessing → O(n)

Each query → O(1)

Range Sum Formula

Use this:

S(L,R)=prefix[R]−prefix[L−1]

Special case:

If L = 0 → just prefix[R]

Implementation

public static int rangeSum(int[] prefix, int L, int R) {

if (L == 0) return prefix[R];

return prefix[R] - prefix[L-1];

}

The Real Insight

Do work once → reuse many times

Instead of solving each query separately,

you precompute smartly.

Applications

Range sum…